二分查找(leetcode easy 704)、移除元素(leetcode easy 27)

二分查找

题目链接:https://leetcode.cn/problems/binary-search/

思路:

1. 暴力法: 直接遍历一边数组查找元素. 此方法适用于任何数组查找.(时间复杂度O(n)、空间复杂度O(1)).
2. 二分查找: 因为是有序数组, 对数组取中间元素, 可以通过比较该元素与目标值得知目标值在该中间元素的左边或者是右边. (时间复杂度O(logn)、空间复杂度O(1)).

注意事项(不考虑暴力法):

1. 边界的取值范围, 左闭右闭区间([0, nums.length-1]), 左闭右开区间([0, nums.length]). 这两种取值方法会影响到边界的更新.

2. while循环条件

   • 对于左闭右闭区间, 当[left, right](left == right)时, 此区间有效(区间内有值), 故而此时循环条件应该是left <= right.
   • 对于左闭右开区间, 当[left, right)(left == right)时, 此区间无效, 故而此时循环条件为left < right.

3. 边界的更新

   • 对于左闭右闭区间(即目标值可能处于最左边或者最右边)来说, 当中间值与目标值不等时(即需要更新边界), 中间值需被舍弃掉, 所以左边界更新为中间值索引+1, 右边界更新为中间值索引-1.
   • 对于左闭右开区间(目标值可能处于最左边)来说, 当中间值与目标值不等且目标值处于中间值左边时, 此时中间值不能被舍弃, 右边界更新为中间值索引.

代码实现(左闭右闭、java):

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (right >= left) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

移除元素

题目链接:https://leetcode.cn/problems/remove-element/

思路:

1. 暴力法: 双层循环, 外循环遍历数组, 当遍历到目标值时进行内循环将后续所有元素向前移动一位. (时间复杂度O(n^2)).
2. 进行一次遍历, 一个索引指向数组末尾(这个索引还记录了删除后剩余数组长度), 遍历到目标值后, 将索引指向元素替换到该位置并将指向末尾的索引进行-1操作使得. (因题目提示可以不考虑剩余元素顺序,故可采取此方法). (时间复杂度O(n)).

注意事项(不考虑暴力法):

1. 当将末尾元素替换到遍历到的目标值位置时, 如果该末尾元素也是等于目标值的, 此时相当于未删除,但是末尾索引是被更新了的, 所以只需要对该元素再进行一次判断即可.

代码实现(java)

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;	// len：记录数组实际需要遍历的长度，以及记录移除元素后剩余长度
        int i = 0;
        while (i < len) {
            // 判断到当前遍历元素是val后，将数组"末尾"的元素替换到当前元素
            if (nums[i] == val) {
                nums[i] = nums[--len];
                // if内部无"i++"操作的原因是需要考虑从数组后方替换过来的元素等于val的情况需要对当前位置再进行一次判断
                continue;
            }
            i++;
        }
        return len;
    }
}