数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

特点：

随机访问快： 只要知道下标，可以在 $O(1)$ 时间内找到元素。

增删成本高： 数组大小固定。如果你要在中间插入一个数，后面的所有元素都要往后挪。

二分：

数组是 .length（属性），字符串是 .length()（方法）

错误：

image-20260305211931872

问题：

  1. mid 只在循环外部计算了一次，循环内部没有更新

  2. 指针移动方式错误（每次只移动一步，而不是折半）

改正：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 在循环内部重新计算 mid
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;   // 折半缩小右边界
            } else {
                left = mid + 1;    // 折半缩小左边界
            }
        }
        return -1;
    }
}
移除元素

https://leetcode.cn/problems/remove-element/

暴力都写错了。。。

image-20260306081943502

问题太多，重新写

Arrays.sort(nums)

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

注意length–和i–的位置！

这个可以用快慢指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

不是int [] result=new int(nums.length);是int [] result=new int[nums.length];

img