Leetcode-刷题记录-05-普通数组

2025-03-09 约 1267 字预计阅读 3 分钟

https://bing.ee123.net/img/rand?artid=146139729

Leetcode 刷题记录 05 —— 普通数组

本系列为笔者的记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

01 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
    }
};

方法一：动态规划（卡达尼算法）

声明 pre ，存储 x 之前的最大子数组和， pre = max(pre+x, x)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, ans = nums[0];
        for(const auto& x: nums){
            pre = max(pre+x, x);
            ans = max(ans, pre);
        }
        return ans;
    }
};

方法二：二分 + 递推

建立结构体 Status ，包含 iSum, lSum, rSum, mSum
采用二分，不断切割区间 [l, r] ，进行递归，快速下降后缓慢回升
注： if(l == r) return (Status) {a[l], a[l], a[l], a[l]};

class Solution {
public:
    struct Status{
        int iSum, lSum, rSum, mSum;
    };

    //缓慢回升：递推
    Status pushUp(Status l, Status r){
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {iSum, lSum, rSum, mSum};
    }

    //快速下降：二分
    Status get(vector<int>& a, int l, int r){
        if(l == r) return (Status) {a[l], a[l], a[l], a[l]};

        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

02 合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        
    }
};

方法：排序

sort 原数组
判断 merged.back()[1] < L ，若成立，则添加区间，若不成立，则更新原区间右端点
注： if(intervals.size() == 0) return {};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 0) return {};
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> merged;
        for(int i=0; i<intervals.size(); ++i){
            int L = intervals[i][0];
            int R = intervals[i][1];
            if(!merged.size() || merged.back()[1] < L) merged.push_back({L, R});
            else merged.back()[1] = max(merged.back()[1], R);
        }
        return merged;
    }
};

03 轮转数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        
    }
};

方法：新建数组

建立新数组 newArr(n) ，存储轮转结果 newArr[(i+k)%n] = nums[i];

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for(int i=0; i<n; ++i){
            newArr[(i+k)%n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
};

nums.assign(newArr.begin(), newArr.end()) 意味着用 newArr 中由 begin() 和 end() 界定的元素范围替换 nums 中原有的元素。

04 除自身以外数组的乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        
    }
};

方法一：左右乘积列表

建立两个数组 leftSup(n) 和 rightSup(n) ，存储 i 左侧和右侧元素乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> leftSup(n);
        leftSup[0] = 1;
        for(int i=1; i<n; ++i){
            leftSup[i] = leftSup[i-1] * nums[i-1];
        }
        
        vector<int> rightSup(n);
        rightSup[n-1] = 1;
        for(int i=n-2; i>=0; --i){
            rightSup[i] = rightSup[i+1] * nums[i+1];
        }
        
        vector<int> ans(n);
        for(int i=0; i<n; ++i){
            ans[i] = leftSup[i] * rightSup[i];
        }
        return ans;
    }
};

方法二：左右乘积列表Plus

建立一个数组 ans(n) ，初始存储 i 左侧元素乘积
从右至左，计算 ans(n) 最终值

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        
        ans[0] = 1;
        for(int i=1; i<n; ++i){
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int R = 1;
        for(int i=n-1; i>=0; --i){
            ans[i] = ans[i] * R;
            R *= nums[i];
        }
        return ans;
    }
};

05 缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        
    }
};

方法一：哈希映射

时间复杂度 O(n)、空间复杂度 O(n)

方法二：枚举

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

方法三：数组改造哈希表

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

遍历数组，所有复数改为 n + 1
遍历数组，判断 abs(nums[i]) <= n ，执行 nums[flag - 1] = -abs(nums[flag - 1]);
遍历数组，若每个数都是负数，则答案为 n + 1 ，否则为第一个整数位置加一

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        //改负数
        for(int i=0; i<n; ++i){
            if(nums[i] <= 0) nums[i] = n + 1;
        }
        
        //添负号
        for(int i=0; i<n; ++i){
            int flag = abs(nums[i]);
            if(flag <= n) nums[flag - 1] = -abs(nums[flag - 1]);
        }
        
        for(int i=0; i<n; ++i){
            if(nums[i] > 0) return i + 1; //精髓在负号
        }
        return n + 1;
    }
};

方法四：置换

遍历数组，判断 nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] ，交换两数，执行 swap(nums[nums[i] - 1], nums[i])
遍历数组，若 nums[i] != i + 1 ，则答案为 i + 1 , 否则为 n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
         int n = nums.size();
        
        for(int i=0; i<n; ++i){
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        
        for(int i=0; i<n; ++i){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return n + 1;
    }
};

① 为什么 nums[nums[i] - 1] != nums[i] 改成 nums[i] - 1 != i 会导致执行超过时间限制？

nums[nums[i] - 1] != nums[i] 可能是位置不同但数值相同，导致无限循环交换。

② 为什么 nums[i] != i + 1 改成 nums[i] - 1 != i 会导致执行错误？

以 nums[i] - 1 作为索引进行比较时，可能会涉及到为负数或超出范围的索引，若 nums[i] 是负数或 0 ， nums[i] - 1 是非法索引，可能导致未定义行为。

文章部分代码来源于力扣（LeetCode）