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

704. 二分查找 题目

解题思路

这道题是有序数组，并且没有重复的元素，可以考虑采用二分法进行解答，故想到解法如下：

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

首先考虑到目标值在数组范围的情况，然后排除掉
然后考虑首尾是目标值的情况，然后排除掉
最后利用二分法，得到想要的结果

看完解析后的思路

解析
二分法比较重要的就是弄清边界条件，主要分为两种

• 左闭右闭[left,right]
• 左闭右开[left,right)

左闭右闭的解法如下

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

左闭右开的解法如下

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

总结

二分法主要弄清楚区间的定义，做好边界的处理就好

27. 移除元素 题目

解题思路

考虑到数据能直接删除，如果遍历到指定元素后，对数据进行删除操作会比较麻烦，所以考虑是遍历到非指定元素的值后，将值从头到尾赋值到数组上，故解法如下

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

看完解析后的思路

解析
有种 相向双指针法 是之前没想到的，通过双向的遍历，从尾部将不等于指定的元素赋值到从头部查找到的等于指定元素位置，解法如下

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

总结

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法