今日学习文章：数组理论基础

LeetCode704.二分查找

题目链接：LeetCode704.二分查找

二分法适用：有序且无重复的数组下标查找 

时间复杂度：O(logn)    

空间复杂度：O(1)

思路：利用循环，先寻找到数组的中间值 nums[mid] ,再将其与target进行比较，若 nums[mid] > target 则我们所找的值在中间值的左边；此时，我们将距中间值左边一个单位的元素作为新的右端值，之后再求中间值。若nums[mid] < target 则我们所找的值在中间值的右边；此时，我们将距中间值右边一个单位的元素作为新的左端值，之后再求中间值。若nums[mid] = target 则得到我们所要查找的目标值的下标mid。以此类推，通过不断二分来寻找目标元素下标值。

左闭右闭： 

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

左闭右开：

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

小结：

1.当target处于左闭右闭区间[left,right]时，存在left == right的情况，因此循环条件便需要left <= right;此时，因右端为闭区间，数组右端元素的下标right不能越界，故right的值为数组长度减一，即 right = size – 1。

2.当target处于左闭右开区间[left,right）时，此时不存在left == right的情况，只需要循环条件为left < right便可执行循环，而因右端为开区间，数组右端元素的下标不等于right，故right的值可以为数组长度，即 right = size。

 LeetCode27.移除元素

题目链接：LeetCode27.移除元素

 暴力解法：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for(int i = 0;i < size;i++)
        {
            if(nums[i] == val)
            {
                for(int j = i+1;j < size;j++)
                {
                    nums[j - 1] = nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
};
​

时间复杂度：O(n²)    

空间复杂度：O(1) 

思路：先算出数组总长度，之后用两个for循环进行遍历比较，如果数组元素等于目标值，则将该数组后一个元素覆盖当前数组元素，并将数组总长度减一。最后得出进行移除后数组的长度与新的数组。

小结：该解法没有什么太多的技巧，进行遍历即可，但是所占用的内存大，时间复杂度更高，不推荐使用。

快慢指针：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int slow = 0;
        for(int fast = 0;fast < size;fast++)
        {
            if(nums[fast] != val)
            {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

时间复杂度：O(n)     

空间复杂度：O(1) 

思路：分别设定快指针fast用于与目标值进行比较；慢指针slow用于更新数组元素；从而将两个for循环减少为一个for循环。

小结：快指针和慢指针在应用中的作用不同：快指针通过对比寻找新数组的元素，慢指针则接收新数组的元素并更新新数组下标位置。本质上是对同一个数组进行操作，而原数组元素的相对位置并没有发生改变；该解法有效降低了时间复杂度。