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

704. 二分查找

题目链接：704. 二分查找

文档讲解：代码随想录（programmercarl.com）

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找

状态：已解决

一、思路

        题目中已经点明了使用二分查找的方法，在升序数组 nums 中寻找目标值 target 。每次选取查找区间的中点的值与 target 进行比较，根据两者的大小关系可以进一步确定 target 可能存在的范围，缩小查找区间。每次查找都可以将查找区间缩小一半。

二、解法

方法：二分查找

        设置查找区间的左右端点，区间的左端点记作 p1 ，区间的右端点记作 p2 。对于查找区间中任意下标 i 位置的值，有以下三种情况：

        （1）若，则 i 为所求值，返回 i ；

        （2）若，则 target 所在区间为 i 右侧，更新 p1 为 i ；

        （3）若，则 target 所在区间为 i 左侧，更新 p2 为 i 。

        选取 i 为查找区间的中点 mid ，即。

        判断停止条件如下：

        （1），左开右开：

        （2），左闭右开：

        （3），左闭右闭：

Java代码如下：

        以为例：

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

 复杂度分析：

        时间复杂度：O(logn)，n为数组长度

        空间复杂度：O(1)

三、难点

（1）判断循环终止条件；

（2）中点。若写成，在数组长度过大时可能会造成 int 类型数据溢出。

27. 移除元素

题目链接：27. 移除元素

文档讲解：代码随想录（programmercarl.com）

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素

状态：已解决

一、思路

        首先想到暴力求解法，即遍历数组，找到与 val 相等的值后将其右侧所有元素左移，但时间复杂度较大。使用偏移量法记录每个元素偏移的位数，可以减少元素移动次数。还可以使用双指针法，定位目标值的位置，将其右侧的值填补进来，即可保证非目标值填充在数组的左侧。

二、解法

方法一：偏移量法

        设置一个额外的数组 py[nums.length] 来存储 nums 中每个数据的偏移量，即需要左移的位数。

        设置初始偏移量 p=0 ，遍历数组nums ，判断其中每个数据 nums[i] 是否与 val 相等，若相等，位于数组中其右侧的数据都需向左移动一位，则偏移量 p++ 。对于数组中的每个数据，都将其对应的偏移量存入数组 py 中。

        再次遍历数组 nums ，对于每个不等于 val 的数，将其向左移动，移动的位数即它对应的偏移量。最后返回值即为 p 。

Java代码如下：

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length==0){
            return 0;
        }
        int[] py = new int[nums.length];
        int p=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==val){
                p++;
            }
            py[i]=p;
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=val){
                nums[i-py[i]]=nums[i];
            }
        }
        return nums.length-p;
    }
}

复杂度分析：

        时间复杂度：O(n)，n为数组长度

        空间复杂度：O(n)，n为数组长度

        考虑到偏移量的计算可以与数组的移动一起完成，就不需要使用额外的数组来存储每个数据的偏移量，代码可以改进为如下形式：

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

复杂度分析：

        时间复杂度：O(n)，n为数组长度

        空间复杂度：O(1)

 

方法二：双指针法（元素相对位置不变）

        维护两个指针 left 和 right ，left 指向数组要赋值的位置， right 指向当前判断的元素。初始 left 和 right 都指向0。 right 遍历数组 nums 。

        （1）当 nums[right]=val 时，right++ ；

        （2）当 nums[right]!=val 时，将 right 位置的值赋给left位置，right++，left++。

Java代码如下：

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length==0){
            return 0;
        }
        int left=0;
        for(int right=0;right<nums.length;right++){
            if(nums[right]!=val){
                nums[left]=nums[right];
                left++;
            }
        }
        return left;
    }
}

复杂度分析：

        时间复杂度：O(n)，n为数组长度

        空间复杂度：O(1)

方法三：双指针法（元素相对位置变化）

        题中说明不需保证元素的相对位置不发生变化，那么从左至右将目标值位置填充上其右侧的非目标值即可，可以减少数组操作的次数。

        维护两个指针 left 和 right ，left 指向数组要赋值的位置， right 指向当前判断的元素。初始 left 指向0，right 指向 nums.length-1。当left与right不重合时：

        （1）当 nums[left]=val 时，将 right 位置的值赋给left位置，right-- ；

        （2）当 nums[left]!=val 时，left++。

Java代码如下：

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length==0){
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            if(nums[left]==val){
                nums[left]=nums[right];
                right--;
            }else{
                left++;
            }
        }
        return left;
    }
}

复杂度分析：

        时间复杂度：O(n)，n为数组长度

        空间复杂度：O(1)

三、难点

（1）尽可能在时间复杂度上对算法进行优化，使用尽可能小的时间复杂度，在本题中尽可能减少移动元素的次数。

（2）循环的终止条件需要仔细考量。