力扣刷题|704. 二分查找、27. 移除元素

LeetCode 704.二分查找

题目链接?： LeetCode 704.二分查找

思路

二分法涉及到挺多的边界问题，首先就是要定义好区间，区间的定义就是不变量

区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

• 二分查找的前提条件

1. 数组为有序数组

2. 数组中没有重复元素

代码实现

左闭右闭

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

左闭右开

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

对区间的定义不同主要会导致三处的变化：指针位置的定义、while的判断条件、指针更新的方式

下面来分析时间复杂度和空间复杂度

时间复杂度：时间复杂度就是算法执行语句的次数

假设一共有n个元素，每次查找的区间大小就是n, n/2, n/4, ..., n/2^k（其中k就是循环的次数）

最坏的情况就是还剩一个元素，n/2^k = 1 得k = log2n（以2为底的对数）

因此时间复杂度为O(log2n)

空间复杂度：空间复杂度就是算法所需的存储空间

因为变量只创建一次，所以 空间复杂度 为O(1)

LeetCode 27.移除元素

题目链接?： LeetCode 27.移除元素

思路

数组在内存空间的地址是连续的，删除其实就等于覆盖

主要有两种方法：

暴力解法：两层for循环，一是循环遍历数组元素，二是循环更新元素

双指针法：定义快慢指针，在一个for循环下完成遍历

• 快指针：寻找新数组的元素，新数组就是不含有要删除的元素的数组

• 慢指针：指向更新，新数组下标的位置

代码实现

暴力解法

public int removeElement(int[] nums, int val) {
    int length = nums.length;
    for (int i = 0; i < length; i++) {
        if (nums[i] == val){
            for (int j = i + 1; j < length; j++) {
                nums[j - 1] = nums[j];
            }
            i--;
            length--;
        }
    }
    return length;
 }

时间复杂度：O(n^2)

空间复杂度：O(1)

双指针法

 public int removeElement(int[] nums, int val) {
    int slowIndex = 0;
    for (int fastIndex = 0;fastIndex < nums.length;fastIndex++){
        if (nums[fastIndex] != val){
            nums[slowIndex] = nums[fastIndex];
            slowIndex++;
        }
    }
    return slowIndex;
}

时间复杂度：O(n)

空间复杂度：O(1)