数组

数组基本概念

基本定义

• 线性结构
• 相同类型
• 固定大小

特点

• 访问速度快：$O(1)$
• 插入与删除效率低，需要移动其他元素，时间复杂度$O(n)$

备注

在C++中，需要区分vector与array，vector底层为array，其本身严格讲为：容器。

常见算法与代码

二分查找

对于$n$个元素的有序数组$nums$与目标值$target$，查找数组中是否存在目标值，如果存在，返回目标元素下标。数组元素不重复，下标唯一。

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

删除元素

给定一个数组$nums$和一个值$val$，你需要原地移除所有数值等于$val$的元素，并返回移除后数组的新长度。

注意，数组内存空间连续，删除元素需要将后续元素向前移动进行覆盖，时间复杂度高。

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
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;
    }
};

时间复杂度较高，特别是当重复元素较多的情况下。可使用快慢指针进行优化，不相等原地赋值一起往前走；相等，快指针先走，慢指针等着被不相等的元素去覆盖他。

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) 
        {
            if (val != nums[fastIndex]) 
            {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

有序数组的平方

给你一个按非递减顺序排序的整数数组$nums$，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。数组包含负数。

平方+排序=暴力

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) 
    {
        for (int i = 0; i < A.size(); i++) 
        {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); 
        return A;
    }
};

要不想想二次函数？用双指针。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) 
    {
        int k = A.size() - 1;
        vector<int>ans(A.size(), 0);
        int left = 0, right = k;
        while(left <= right)
        {
            if(A[left]*A[left] > A[right]*A[right])
            {
                ans[k--] = A[left]*A[left];
                left--;
            }
            else
            {
                ans[k--] = A[right]*A[right];
                right--;
            }
        }
        return ans;
    }
};

螺旋矩阵Ⅱ

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

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};