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

前言
状态：可以通过
更新

1	24.04.17 初始记录

初步题解

704 二分查找

题目链接：https://leetcode.cn/problems/binary-search/

public class LE704 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int[] nums = Arrays.stream(scanner.nextLine().split(","))  
                .mapToInt(Integer::parseInt)  
                .toArray();  
        int target = Integer.parseInt(scanner.nextLine());  
        System.out.println(search(nums, target));  
    }  
  
    public static int search(int[] nums, int target) {  
        for (int i = 0, j = nums.length - 1; i <= j; ) {  
            int k = (i + j) / 2;  
            if (nums[k] == target) {  
                return k;  
            }  
            if (nums[k] > target) {  
                j = k - 1;  
            } else {  
                i = k + 1;  
            }  
        }  
  
        return -1;  
    }  
}

27 移除元素

题目链接：https://leetcode.cn/problems/remove-element/

public class LE27 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int[] nums = Arrays.stream(scanner.nextLine().split(","))  
                .mapToInt(Integer::parseInt)  
                .toArray();  
        int val = Integer.parseInt(scanner.nextLine());  
        System.out.println(removeElement(nums, val));  
    }  
  
    public static int removeElement(int[] nums, int val) {  
        int i, j;  
        for (i = 0, j = nums.length - 1; i <= j ; ) {  
            // 第一次修改 -> if改为while  
            // 第三次修改 -> 加上j的边界值限制, 不然会数组越界  
            while (j >= 0 && nums[j] == val) {  
                j--;  
            }  
            while (i <= nums.length - 1 && nums[i] != val) {  
                i++;  
            }  
            // 第二次修改 -> 加上i < j的判断, 否则最后一次交换会把数组换乱  
            if (i < j) {  
                int temp = nums[j];  
                nums[j] = nums[i];  
                nums[i] = temp;  
            }  
        }  
        return i;  
    }  
}

看讲解

704 二分查找

文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

public static int search(int[] nums, int target) {  
    for (int i = 0, j = nums.length - 1; i <= j; ) { 
	    // 这里需要写成这种方式防止整数溢出
	    // 或者也可以写成 int k = i + ((j - i) >> 1);
	    int k = i + (j - i) / 2;
        // int k = (i + j) / 2;  
        if (nums[k] == target) {  
            return k;  
        }  
        if (nums[k] > target) {  
            j = k - 1;  
        } else {  
            i = k + 1;  
        }  
    }  
    return -1;  
}

27 移除元素

文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

其实。。一开始看题目我没有反应过来暴力解法是什么。第一时间当然是想到 iterator().remove()，但是不行。老实说，那个题目里的 O(1) 额外空间我也不知道怎么算的。

暴力解法是双层循环，删除之后的所有都前移。

双指针和我想的也完全不一样，我也不知道我写的这个叫什么。。

public static int removeElement(int[] nums, int val) {  
    int i = 0;  
    for (int j = 0; j < nums.length; j++) {
	    // 当 val == nums[j]时，只有j++
	    // 下一次不相等时，前一个指针的后一位直接指向当前的j，相当于中间的元素都被删除了。
        if (val != nums[j]) {  
            nums[i++]= nums[j];  
        }  
    }  
    return i;  
}

总结

其实都属于已经知道题解方式再去看题，加上是简单算法，所以感觉难度不是很大。（也可能我只是为了找工作，对我来说解出来就 OK）

二分查找

前提：

1、有序数组

2、数组中无重复元素

注意：

整数数值越界的问题