数组总结

LeetCode

发布日期: 2021-09-23

统计

基础的，统计连续出现的1

int findMaxConsecutiveOnes(vector<int>& nums) {
    int cnt = 0, res = 0;
    for (int i = 0; i < nums.size(); i++) {
        cnt = nums[i] ? cnt + 1 : 0;
        res = max(res, cnt);
    }
    return res;
}

统计相同的0和1的子串，尽管是字符串，但思想还是一样的

696-计数二进制子串

int countBinarySubstrings(string s) {
    int pre = 0, cur = 1;
    int count = 0;
    for (int i = 1; i < s.size(); ++i) {
        if (s[i] == s[i - 1]) {
            cur++;   // 记录相同的0或1
        }
        else {
            pre = cur;
            cur = 1; // 出现不同就置1
        }
        if (pre >= cur) count++;    // pre大于cur说明可以匹配
    }
    return count;
}

自己出题，统计排序数组中出现次数最多的数字，不能用哈希表

int findMaxFreq(vector<int>& nums) {
    vector<int> nums = {1, 1, 2, 2, 3, 3, 3};
    int res = 0;
    int cnt = 1;
    for (uint32_t i = 1; i < nums.size(); i++) {
        if (nums[i] == nums[i - 1]) cnt++;  // 边遍历边统计
        else cnt = 1;   // 出现不连续就置1
        res = max(res, cnt);    // 记录最大值
    }
    return res;
}

统计第k大的元素

215-数组中的第k个最大元素

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < nums.size(); ++i) {
        q.push(nums[i]);
        if (q.size() > k) q.pop();  // 超过k个要把最小的出队
    }
    return q.top();
}

统计出现频率最高的k个元素

需要统计所有数字的出现次数，用哈希表
凡是需要最高或最低的k个元素或第k个元素，都要用到优先队列

347-前k个高频元素

class cmp {
public:
    bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs) {
        return lhs.second > rhs.second; // 跟sort不一样，反过来了
    }
};
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    for (auto n : nums) hash[n]++;
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;
    for (auto it = hash.begin(); it != hash.end(); it++) {
        q.push(*it);
        if (q.size() > k) q.pop();  // 大于k个要把最小的出队
    } 
    vector<int> res(k);
    for (int i = k - 1; i >= 0; i--) {
        res[i] = q.top().first;
        q.pop();
    }
    return res;
}

双指针

移除某个特定元素

27-移除元素

method 1: 同向双指针

int removeElement(vector<int>& nums, int val) {
    int l = 0, r = 0;
    while (r < nums.size()) {
        if (nums[r] != val) {
            nums[l] = nums[r];
            l++;
        }
        r++;
    }
    return l;
}

method 2: 反向双指针

int removeElement(vector<int>& nums, int val) {
    if (nums.empty()) return 0;
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        while (l < r && nums[l] != val) l++;
        while (l < r && nums[r] == val) r--;
        swap(nums, l, r);
    }
    return (nums[l] == val ? l : l + 1);
}

保留N个重复项

26/80-删除有序数组中的重复项

int removeDuplicates(vector<int>& nums) {
    if (nums.size() < N) return nums.size();
    int index = N;
    for (int i = N; i < nums.size(); i++) {
        if (nums[i] != nums[index - 1]) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

奇怪的遍历方式

螺旋遍历二维数组，注意区间都要一样左开右闭

54-螺旋矩阵

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    vector<int> res(n * m, 0);
    int n1 = n, m1 = m;
    int offset = 1;
    int startx = 0, starty = 0;
    int cnt = 0;
    int i = 0, j = 0;
    while (n1 > 1 && m1 > 1) {
        i = startx, j = starty;
        for (; j < starty + m - offset; j++) res[cnt++] = matrix[i][j];
        for (; i < startx + n - offset; i++) res[cnt++] = matrix[i][j];
        for (; j > starty; j--) res[cnt++] = matrix[i][j];  // 大于起始位置
        for (; i > startx; i--) res[cnt++] = matrix[i][j];
        n1 -= 2;
        m1 -= 2;
        offset += 2;
        startx++;
        starty++;
    }
    i = startx, j = starty;
    if (n1 == 1 && m1 == 1) res[cnt++] = matrix[i][j];  // 剩一个
    else if (n1 == 1 && m1 > 1) {   // 剩一行
        for (; j < starty + m1; j++) res[cnt++] = matrix[i][j];
    }
    else if (n1 > 1 && m1 == 1) {   // 剩一列
        for (; i < startx + n1; i++) res[cnt++] = matrix[i][j];
    }
    else return res;    // 没剩下，直接返回
    return res;