算法-数组

Keep thinking. / 2024-01-20 / 原文

1. 二分查找 (LeetCode 704)

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

关键：确定合法区间的形式。
常见的有2种：

左闭右闭
左闭右开

// 左闭右闭的写法
// target!=nums[mid]的情况下,left和right都不需要再等于mid
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;
        while (left <= right) {             //左闭右闭的定义下 left=right是合法的
            mid = (left + right) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return -1;
    }
}

2. 删除元素(LeetCode 27)

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

2.1 暴力求解

两层for循环，每发现一个等于val的元素，就把它后面的元素依次往前移动一个位置。

// 暴力解法
class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for(int i = 0; i<size;++i){
            if(nums[i] == val){
                for(int j = i+1; j<size;++j){
                    nums[j-1] = nums[j];
                }
                size--;
                i--;
            }
        }
        return size;
    }
}

2.2 双指针

只需要O(n)的复杂度

slow指向新数组的下标
fast去扫一边数组，找到第一个不等于val的元素，用来填入新数组

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