CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法第一天| 704. 二分查找、27. 移除元素

Posted on

LeetCode 704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// invirants:
// If the target value is within the array to be searched, at any iteration, it stays within [left,right]

// [0, nums.length - 1] is our seaching range
// keep searching until left > right where there is no element left in our range
// mid = (left + right) / 2

/* if nums[mid] > target, since all the elements left in our range are valid, 
 * thus right = mid - 1, as the mid value is impossible to be target now,
 * which is the same with updating the left index.
 */

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

        while(left <= right) {
            mid = (right - left)/2 + left;
            if (nums[mid] == target) {
                ans = mid;
                break;
            }else if (nums[mid] > target ) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return ans;
    }
}

这道题的重点在于循环不变量的确定以及维护，常见的错误点是开闭区间，循环条件，以及循环中左右index的更新。

LeetCode 27.移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int removeElement(int[] nums, int val) {

        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        // note: when left = right, the current pointing element has not 
        // been checked, thus when and only when left > right, we stop checking
        while (leftIndex <= rightIndex) {
            if (nums[leftIndex] != val) {
                leftIndex ++;
            }else {
                nums[leftIndex] = nums[rightIndex];
                rightIndex--;
            }
        }

        return leftIndex;
    }

    /* [0, nums.length)
    * 
    */
    // public int removeElement(int[] nums, int val) {

    //     int leftIndex = 0;
    //     int rightIndex = nums.length;

    //     while (leftIndex < rightIndex) {
    //         if (nums[leftIndex] != val) {
    //             leftIndex ++;
    //         }else {
    //             nums[leftIndex] = nums[rightIndex - 1];
    //             rightIndex--;
    //         }
    //     }

    //     return leftIndex;
    // }
}

这道题使用双指针方法可以达到O(n)的时间复杂度，最一开始我写的版本双指针在同侧，后来思考后发现这样多扫描了一些元素，所以在此之上做了一些优化，使用两个指针对向遍历，当二者相遇后停止。

Note：循环条件的设定仍然和开闭区间有关

LeetCode 35.搜索插入位置

题目要求在数组中查找指定元素，若检索到该元素，返回其索引，若不包含此元素，返回其应该被插入的位置的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 /*
  * try to find the first element in this array which fit a[i] >= target
 	* i.e. nums[pos - 1] < target <= nums[pos]
  */

// @lc code=start
class Solution {
    // public int searchInsert(int[] nums, int target) {
    //     int left = 0;
    //     int right = nums.length - 1;
    //     int mid = 0; 

    //     while (left <= right) {
    //         mid = (right - left) / 2 + left;
    //         if (nums[mid] >= target) {
    //             right = mid - 1;
    //         } else if (nums[mid] < target) {
    //             left = mid + 1;
    //         } 
    //     }
    //     return left;
    // }

    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        int mid = 0; 

        while (left < right) {
            mid = (right - left) / 2 + left;
            if (nums[mid] >= target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } 
        }
        return left;
    }
}

上述同时实现了开闭区间的解法。

一开始一直纠结的一个点是，当nums[mid] >= target时，将right更新为mid - 1会把valid的节点移除出区间，后来思考了一段时间，发现按照这样的更新方法，结束循环时，所有的>=target的元素都在right右侧，即[right + 1, ]，而所有小于target的元素都在left左侧，而退出循环时，总满足left = right + 1, 则left总是指向第一个满足>=target的元素，故而总是返回left即可。