数组理论基础

C/C++

数组是存放在连续内存空间上的相同类型数据集合。多维数组同。
在删除或者增添元素的时候，就难免要移动其他元素的地址。
stl中的vector底层是array，是容器不是数组。

Java

一维数组是内存连续的数据集合。多维不是。

二分查找

力扣——二分查找

需要注意：

  • 使用二分法的条件：1）有序数列 2）无重复元素（二分查找不稳定）
  • 边界问题，是左闭右开还是闭区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search(vector<int>& nums, int target) {
    int left=0,right = nums.size()-1;
    int mid = left+(right-left)/2;
    while(left<=right){
         mid = left+(right-left)/2;
        if(nums[mid]<target){
            left = mid+1;
        }
        else if(nums[mid]>target){
            right = mid-1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

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

移除元素

力扣——移除元素
使用双指针法对目标元素进行移动。双指针通常可以在一个for循环中完成两个for循环的任务

我的实现：

1
2
3
4
5
6
7
8
9
10
int removeElement(vector<int>& nums, int val) {
    int fast=0,slow=0;
    int numSize = nums.size();
    for(;fast<numSize;fast++){
        if(nums[fast] != val){
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

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

针对这道题，如果双指针法的具体运作过程不好理解，不妨这样想：
把原地操作的数组复制一遍，快慢指针分别在两个数组上遍历。当快指针遍历的值不等于删除目标就把该值复制到慢指针指向的数组位置中，当快指针指向的值等于删除目标则跳过该值继续遍历。

有序数组的平方

力扣——有序数组的平方

除了暴力求解（时间复杂度：O(n+nlogn), 空间复杂度：O(1)），还可使用双指针法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> sortedSquares(vector<int>& nums) {
    int size = nums.size();
    vector<int> res = vector<int>(size,0);
    int right = size-1;
    int left =0;
    for(int i = size-1;i>=0;i--){
        int rPow = nums[right]*nums[right];
        int lPow = nums[left]*nums[left];
        if(rPow>lPow){
            res[i] = rPow;
            right--;
        }
        else{
            res[i] = lPow;
            left++;
        }
    }
    return res;
}

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

长度最小的子数组

力扣——长度最小的子数组
滑动窗口。（一种双指针的拓展）精髓在于窗口的移动发生变化的只有头尾两端的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minSubArrayLen(int target, vector<int>& nums) {
    int res = std::numeric_limits<int>::max();
    int sum =0;
    int i=0;
    int size = nums.size();
    int subL = 0;
    for(int j = 0; j<size; j++){
        sum += nums[j];
        while(sum>=target){
            subL = j-i+1;
            res = subL<res ? subL : res;
            sum -= nums[i++];
        }
    }
    return res == std::numeric_limits<int>::max() ? 0 : res;
}

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

螺旋矩阵

力扣——螺旋矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res = vector<vector<int>>(n,vector<int>(n,0));

    int startX = 0;
    int startY = 0;
    int loop = n/2;
    int mid = n/2;
    int count =1;
    int offset = 1;
    int i,j;
    while(loop--){
        i = startX;
        j = startY;

        for(i;i<n-offset;i++){
            res[j][i] = count;
            count ++;
        }
        for(j;j<n-offset;j++){
            res[j][i] = count;
            count ++;
        }
        for(i;i>startX;i--){
            res[j][i] = count;
            count ++;
        }
        for(j;j>startY;j--){
            res[j][i] = count;
            count ++;
        }

        startX += 1;
        startY += 1;
        offset ++;
    }

    if(n%2){
        res[mid][mid] = count;
    }
    return res;
}

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

区间和

力扣——区间和

空间换时间，使用前缀和。创建一个新的数组，其中第i个元素记录原数组前i个元素的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int arrayL=0;
    cin >> arrayL;
    
    vector<int> array = vector<int>(arrayL,0);
    vector<int> sum = vector<int>(arrayL,0);
    int pre = 0;
    for(int i=0;i<arrayL;i++){
        int n = 0;
        cin>>n;
        
        array[i] = n;
        pre += n;
        sum[i] = pre;
    }
    
    int a,b;
    while(cin >> a >> b){
        int output = 0;
        if(a<=0) {output = sum[b];}
        else{output = sum[b]-sum[a-1];}
        printf("%d\n",output);
    }
}

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

开发商购买土地

力扣——开发商购买土地

前缀和，计算每行每列的总和，接着算出最小差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main(){
    int n=0,m=0;
    cin>>n>>m;
    vector<vector<int>> area(n,vector<int>(m,0));
    int total = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> area[i][j];
            total += area[i][j];
        }
    }
    
    vector<int> horizontal = vector<int>(n,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            horizontal[i] += area[i][j];
        }
    }
    
    vector<int> vertical = vector<int>(m,0);
    for(int j=0;j<m;j++){
        for(int i=0;i<n;i++){
            vertical[j] += area[i][j];
        }
    }
    
    
    int res = INT_MAX;
    int hTotal =0;
    for(int i=0;i<n;i++){
        hTotal += horizontal[i];
        int offset = abs(total-hTotal-hTotal);
        res = min(res , offset);
    }
    
    int vTotal = 0;
    for(int i=0;i<m;i++){
        vTotal += vertical[i];
        int offset = abs(total-vTotal-vTotal);
        res = min(res,offset);
    }
    
    printf("%d\n",res);
}

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

总结

基础知识

数组是存放在连续内存空间上的相同类型数据集合。多维数组同。
在删除或者增添元素的时候，就难免要移动其他元素的地址。
stl中的vector底层是array，是容器不是数组。

数组算法题目中的常用方法

  • 二分查找
  • 双指针法
  • 滑动窗口
  • 前缀和
  • 模拟行为（螺旋矩阵那道题，找好区间，控制好索引）