代码随想录 | Day 1 | LC 27 移除元素、704 二分查找

704. 二分查找

题目

解法1:纯遍历

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target)
                return i;    
        }
        return -1;
    }
}

解法2:二分法

双闭区间的解法,此处的left=right时的情况我code的时候拉出来单独处理了(其实可以<=一起写进while条件的)

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

27. 移除元素

解法1 直接for循环

要注意的点就是length--和i--;别忘了,第一次写的时候没写,没跑出来

class Solution {
     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; j <length-1 ; j++) {
                    nums[j]=nums[j+1];
                }
                length--;//如果走进了这个if,即说明一定有元素被删除了
                i--;//i--是因为数组元素整体前移了,判断的下标也得前移
                // 例a[0]->a[-1],此时a[-1]会再++变成a[0],以实现对删除后数组的判断
            }

        }
        return length;//返回移除后数组的新长度
    }
}

解法2 双指针(重要)

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length==0 || nums==null){//提示：0 <= nums.length <= 100(所以这个边界的base case不能漏)
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] != val) {//left<right也是这个while的退出条件,不可省略。例:{3,3,3}
                left++;//不等于的值,应当保留下来,left++左区右移
            }
            while (left < right && nums[right] == val) {
                right--;//等于的值,是没用的值,right--往左移,丢弃
            }
            //a[首]与a[末]交换位置,将末位置的元素往前扔进行判断
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        // if (nums[left] == val) {
        //     return left;//数组下标从零开始
        // }
        return (nums[left] == val) ? left : left +1;
    }
}