leetcode-数组

发表于 2022-09-21 分类于 leetcode Disqus：

leetcode 中数组相关的题型

数组理论基础

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

leetcode-array-1

数组下标都是从0开始的。
数组内存空间的地址是连续的

因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

leetcode-array-2

数组的元素是不能删的，只能覆盖。

二维数组结构

leetcode-array-3

那么二维数组在内存的空间地址是连续的么？

不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。

我们来做一个实验，C++测试代码如下：

void test_arr() {
    int array[2][3] = {
		{0, 1, 2},
		{3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

测试地址为

0x7ffee4065820 0x7ffee4065824 0x7ffee4065828 0x7ffee406582c 0x7ffee4065830 0x7ffee4065834 注意地址为16进制，可以看出二维数组地址是连续一条线的。

0x7ffee4065820 与 0x7ffee4065824 差了一个4，就是4个字节，因为这是一个int型的数组，所以两个相邻数组元素地址差4个字节。

0x7ffee4065828 与 0x7ffee406582c 也是差了4个字节，在16进制里8 + 4 = c，c就是12。

leetcode-array-5

Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。

所以看不到每个元素的地址情况，这里我以Java为例，也做一个实验。

public static void test_arr() {
    int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9,9,9}};
    System.out.println(arr[0]);
    System.out.println(arr[1]);
    System.out.println(arr[2]);
    System.out.println(arr[3]);
}

输出的地址为：

[I@7852e922
[I@4e25154f
[I@70dea4e
[I@5c647e05

这里的数值也是16进制，这不是真正的地址，而是经过处理过后的数值了，我们也可以看出，二维数组的每一行头结点的地址是没有规则的，更谈不上连续。

leetcode-array-4

二分查找

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

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

示例 2:
输入: nums = [-1, 0, 3, 5, 9, 12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路

二分法前提条件

有序数组
数组中无重复元素

循环不变量规则: 在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。

左闭右闭即[left, right]

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

例如在数组：1, 2, 3, 4, 7, 9, 10中查找元素2，如图所示：

leetcode-array-6

function search(nums: number[], target: number): number {
    let middle: number = 0;
    let left: number = 0;
    let right: number = nums.length - 1;
    while (left <= right) {
        // 位运算 + 防止大数溢出
        middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
};

左闭右开即[left, right)

while (left < right)，这里使用 < , 因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

function search(nums: number[], target: number): number {
    let middle: number = 0;
    let left: number = 0;
    let right: number = nums.length;
    while (left < right) {
        // 位运算 + 防止大数溢出
        middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
};

移除元素

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

示例 1:
给定 nums = [3,2,2,3], val = 3, 
函数应该返回新的长度 2, 
并且 nums 中的前两个元素均为 2。

示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5,
并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

思路

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

暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素，第二个for循环更新数组。

leetcode-array-7

function removeElement(nums:number[], val:number):number{
    let size = nums.length;
    for (let i = 0; i < size; i++) {
        if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
            for (let j = i + 1; j < size; j++) {
                nums[j - 1] = nums[j];
            }
            i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
            size--; // 此时数组的大小-1
        }
    }        
    return size;

时间复杂度：O(n^2)
空间复杂度：O(1)

双指针法

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

leetcode-array-8

function removeElement(nums: number[], val: number): number {
    let slowIndex: number = 0, fastIndex: number = 0;
    while (fastIndex < nums.length) {
        if (nums[fastIndex] !== val) {
            nums[slowIndex++] = nums[fastIndex];
        }
        fastIndex++;
    }
    return slowIndex;
};

时间复杂度：O(n)
空间复杂度：O(1)

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：
输入：s = 7, nums = [2, 3, 1, 2, 4, 3]
输出：2
解释：子数组 [4, 3] 是该条件下的长度最小的子数组。

思路

暴力解法

两个for循环，然后不断的寻找符合条件的子序列。

function minSubArrayLen(target: number, nums: number[]): number {
    let result = 0;
    let sum = 0; // 子序列的数值之和
    let subLength = 0; // 子序列的长度
    for (int i = 0; i < nums.length; i++) { // 设置子序列起点为i
        sum = 0;
        for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
            sum += nums[j];
            if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                subLength = j - i + 1; // 取子序列的长度
                result = result < subLength ? result : subLength;
                break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
            }
        }
    }
    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    return result == INT32_MAX ? 0 : result;
}

时间复杂度：O(n^2) 空间复杂度：O(1)

滑动窗口

不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

首先要思考如果用一个 for 循环，那么应该表示滑动窗口的起始位置，还是终止位置。

如果只用一个 for 循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入暴力解法的怪圈。

所以只用一个 for 循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。

那么问题来了，滑动窗口的起始位置如何移动呢？

这里还是以题目中的示例来举例，s=7，数组是 2，3，1，2，4，3，来看一下查找的过程：

leetcode-array-10

在本题中实现滑动窗口，主要确定如下三点：

窗口定义：满足其和 ≥ s 的长度最小的连续子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

leetcode-array-11

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。

function minSubArrayLen(target: number, nums: number[]): number {
    let result = Number.MAX_SAFE_INTEGER;
    let left = 0;
    let right = 0;
    let sum = 0;
    while (right < nums.length) {
        sum += nums[right];
        while (sum >= target) {
            result = Math.min(result, right - left + 1);
            sum -= nums[left];
            left++;
        }

        right++;
    }

    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    return result === Number.MAX_SAFE_INTEGER ? 0 : result;
};

时间复杂度：O(n) 空间复杂度：O(1)

螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

leetcode-array-12

1
2
3

示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

1
2
3

示例 2：
输入：n = 1
输出：[[1]]

解题思路

模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上由外向内一圈一圈这么画下去，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则。

左闭右开的原则画法：

leetcode-array-14

这里每一种颜色，代表一条边，每一个拐角处让给新的一条边来继续画。

function generateMatrix(n: number): number[][] {
    let loopNum: number = Math.floor(n / 2);
    const resArr: number[][] = new Array(n).fill(1).map(i => new Array(n));
    let chunkNum: number = n - 1;
    let startX: number = 0;
    let startY: number = 0;
    let value: number = 1;
    let x: number, y: number;
    while (loopNum--) {
        x = startX;
        y = startY;
        while (x < startX + chunkNum) {
            resArr[y][x] = value;
            x++;
            value++;
        }
        while (y < startY + chunkNum) {
            resArr[y][x] = value;
            y++;
            value++;
        }
        while (x > startX) {
            resArr[y][x] = value;
            x--;
            value++;
        }
        while (y > startY) {
            resArr[y][x] = value;
            y--;
            value++;
        }
        startX++;
        startY++;
        chunkNum -= 2;
    }
    if (n % 2 === 1) {
        resArr[startX][startY] = value;
    }
    return resArr;
}

总结

leetcode-array-14

参考

数组理论基础
 二分查找
 移除元素
 长度最小的子数组
 螺旋矩阵II
数组总结篇

本文作者：雪糕
本文地址： https://blooddot.cool/posts/b702bc87/
版权声明：转载请注明出处！

雪糕啊哈哈

leetcode-数组

数组理论基础

二维数组结构

二分查找

思路

左闭右闭即[left, right]

左闭右开即[left, right)

相关题目推荐

移除元素

思路

暴力解法

双指针法

相关题目推荐

长度最小的子数组

思路

暴力解法

滑动窗口

相关题目推荐

螺旋矩阵 II

解题思路

相关题目推荐

总结

参考