【力扣刷题】Day01——数组基础

---

1. 二分查找

题目链接：704. 二分查找 - 力扣（LeetCode）

思路：模板题、可以二分找出第一个大于等于target的数的位置，若相等则存在反之不存在

• 时间复杂度：O(logN)

Code

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        } 
        if(nums[l] != target) return -1;
        else return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 移除元素

题目链接：27. 移除元素 - 力扣（LeetCode）

方法：数组重新覆盖

题目要求不能使用额外空间，那我们就在之前的数组上进行修改重新赋值即可，遇到val跳过，反之重新赋值给原数组。

• 时间复杂度O(n)，空间复杂度：O(1)

Code

class Solution {
    public int removeElement(int[] nums, int val) {
        int cnt = 0;
        for(int i = 0; i < nums.length; i ++){
            if(nums[i] == val) continue;
            nums[cnt ++] = nums[i]; 
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10