【算法】代码随想录之数组

文章目录

前言

一、二分查找法（LeetCode--704）

二、移除元素（LeetCode--27）

三、有序数组的平方（LeetCode--977）

四、长度最小的子数组（LeetCode--209）

五、螺旋矩阵II（LeetCode--59）

前言

跟随代码随想录，学习数组相关的算法题目，记录学习过程中的tips。

一、二分查找法（LeetCode--704）

【1】算法功能：在有序数组中，查找指定元素，时间复杂度为O(log N)。

【2】算法思想：定义首尾指针分别指向数组的首尾元素，若中间元素的值小于目标值则将首指针移动至中间元素右侧，若中间元素的值大于目标值则将尾指针移动至中间元素的左侧，若相等则返回下标。

【3】代码实现：在左闭右闭的区间内查找。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
};

【4】易错点：①注意while循环的判定条件；②注意high的更新条件。

二、移除元素（LeetCode--27）

在之前的刷题中已经遇到过，且代码随想录的解法与当时我的初次解法相同，见【LeetCode算法】第27题：移除元素-CSDN博客。

三、有序数组的平方（LeetCode--977）

【1】题目描述：

【2】解决思想：首先，找到正负元素的分界线，利用双指针法来解决。i指针指向最后一个负元素，j指针指向第一个正元素。每次比较i和j元素的大小，谁小就加入目标数组中。i指针向左移动，j指针向右移动。

【3】C++代码：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ret;//最终返回的数组
        //找到首个>=0的元素(分界线)
        int k = 0;
        int len = nums.size();
        while (k < len && nums[k] < 0) {
            ++k;
        }
        //双指针法：i从k处往左，j从k处往右
        int i = k - 1, j = k;
        while (i >= 0 || j < len) {
            if (i < 0) {
                ret.push_back(nums[j] * nums[j]);
                ++j;
            } else if (j >= len) {
                ret.push_back(nums[i] * nums[i]);
                --i;
            } else if (abs(nums[i]) < abs(nums[j])) {
                ret.push_back(nums[i] * nums[i]);
                --i;
            } else {
                ret.push_back(nums[j] * nums[j]);
                ++j;
            }
        }
        return ret;
    }
};

【4】时间复杂度：O(N)。

【5】空间复杂度：O(1)，不算目标数组ret。

四、长度最小的子数组（LeetCode--209）

【1】题目描述：

【2】解决思想：滑动窗口。定义两个指针分别指向滑动窗口的起始位置和终止位置。在主循环中，让终止位置不断后移，每次后移均加上扫过的元素值。当累加值大于等于目标值时，循环缩小起始位置（为了找到最小的数组长度）。

【3】C++代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0;//滑动窗口起始位置
        int sum = 0;
        int ret = INT_MAX;
        //j指向滑动窗口的终止位置
        for (int j = 0; j < nums.size(); ++j) {
            sum += nums[j];
            //循环缩小窗口的起始位置
            while (sum >= target) {
                ret = min(ret, j - i + 1);
                sum -= nums[i++];
            }
        }
        return ret == INT_MAX? 0 : ret;
    }
};

【4】时间复杂度：O(N)。

【5】空间复杂度：O(1)。

【6】启示：当在一个样本空间中寻找一组满足某些条件的连续的子空间时，可以考虑采用滑动窗口方法。

五、螺旋矩阵II（LeetCode--59）

【1】题目描述：

【2】解决思想：如下图所示，每一圈分为四种情况来处理：最上面、最右面、最下面、最左面。同时，每次处理每一条边的时候都遵循左闭右开原则（处理最左边节点，不处理最右边节点），使得每一条边的处理规则都一致。转的圈数是n/2，当n为奇数时最后需要额外添加最中间的一个洞。

【3】C++代码：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ret(n, vector<int>(n, 0));
        int startX = 0, startY = 0;//起始点位置
        int offset = 1;//每转一圈，偏移量+1
        int count = 1;//填入数组中的值
        int circleNum = n / 2;//转的圈数
        for (int k = 0; k < circleNum; ++k) {
            int i, j;
            //第一条边：最上面
            for (j = startY; j < n - offset; ++j) 
                ret[startX][j] = count++;
            //第二条边：最右面
            for (i = startX; i < n - offset; ++i)
                ret[i][j] = count++;
            //第三条边：最下面
            for (; j > startY; --j)
                ret[i][j] = count++;
            //第四条边：最左面
            for (; i > startX; --i)
                ret[i][j] = count++;
            startX++;
            startY++;
            offset++;
        }
        //维度为奇数时，填中间的一格
        if (n % 2 == 1)
            ret[startX][startY] = count;
        return ret;
    }
};

【4】时间复杂度：O(N^2)

【5】空间复杂度：O(1)，不算存储数据的数组。

【6】启示：针对模拟转圈的场景，找到一致性的处理规则很关键。