代码随想录-刷题第一天

说明：之前进行了一刷，在博客记录二刷过程。

704. 二分查找

二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

题目链接：704. 二分查找

思路：采用二分查找，注意确定查找的区间，可以是[left, right]，也可以是[left, right)，两种区间对于边界的操作有所不同。本次确定的区间为[left, right]

时间复杂度：O(logn)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 注意

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1; // 注意
            else if (nums[mid] > target)
                right = mid - 1; // 注意
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

27. 移除元素

题目链接：27. 移除元素

思路：采用相向双指针法，两个指针从数组两端往中间走，遇到要移除的元素直接放到数组最后面。也可以使用快慢指针法，快指针一直走到数据结束，只有当快指针元素不是要删除元素时，快指针元素赋给慢指针元素，并且慢指针往前走一个。

注意：相向双指针法改变数组中元素顺序，快慢指针法不改变数组中元素顺序。

时间复杂度：O(n)

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int fast = 0, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                // 注意这里和有序数组去重的解法有一个细节差异，
                // 我们这里是先给 nums[slow] 赋值然后再给 slow++，
                // 这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，
                // 最后的结果数组长度就是 slow。
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---