LeetCode 热题 100：普通数组

53. 最大子数组和

   给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包罗一个元素），返回其最大和。
  子数组是数组中的一个连续部分。
  示例 1：

1. 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
2. 输出：6
3. 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

复制代码

示例 2：

1. 输入：nums = [1]
2. 输出：1

复制代码

示例 3：

1. 输入：nums = [5,4,-1,7,8]
2. 输出：23

复制代码

提示：
  

• 1 <= nums.length <= 10^5
  
• -10^4 <= nums <= 10^4
  

  **进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

1. int maxSubArray(vector<int>& nums) {
2.     int n = nums.size();
3.     // i结尾最大子数组和
4.     vector<int> dp(n);
5.     dp[0] = nums[0];
6.     int ans = dp[0];
7.     for (int i = 1; i < n; ++i) {
8.         dp[i] = max(dp[i - 1] + nums[i], nums[i]);
9.         ans = max(ans, dp[i]);
10.     }
11.     return ans;
12. }

复制代码

56. 归并区间

   以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals = [starti, endi] 。请你归并全部重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的全部区间 。
  示例 1：

1. 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
2. 输出：[[1,6],[8,10],[15,18]]
3. 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

复制代码

示例 2：

1. 输入：intervals = [[1,4],[4,5]]
2. 输出：[[1,5]]
3. 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

复制代码

提示：
  

• 1 <= intervals.length <= 10^4
  
• intervals.length == 2
  
• 0 <= starti <= endi <= 10^4
  

1. vector<vector<int>> merge(vector<vector<int>>& intervals) {
2.     sort(intervals.begin(), intervals.end());
3.     vector<vector<int>> ans;
4.     for (int i = 0; i < intervals.size(); ++i) {
5.         int left = intervals[i][0], right = intervals[i][1];
6.         if (ans.empty() || ans.back()[1] < left) {
7.             ans.push_back({left, right});
8.         } else {
9.             ans.back()[1] = max(ans.back()[1], right);
10.         }
11.     }
12.     return ans;
13. }

复制代码

189. 轮转数组

   给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
  示例 1:

1. 输入: nums = [1,2,3,4,5,6,7], k = 3
2. 输出: [5,6,7,1,2,3,4]
3. 解释:
4. 向右轮转 1 步: [7,1,2,3,4,5,6]
5. 向右轮转 2 步: [6,7,1,2,3,4,5]
6. 向右轮转 3 步: [5,6,7,1,2,3,4]

复制代码

示例 2:

1. 输入：nums = [-1,-100,3,99], k = 2
2. 输出：[3,99,-1,-100]
3. 解释:
4. 向右轮转 1 步: [99,-1,-100,3]
5. 向右轮转 2 步: [3,99,-1,-100]

复制代码

提示：
  

• 1 <= nums.length <= 10^5
  
• -2^31 <= nums <= 2^31 - 1
  
• 0 <= k <= 10^5
  

1. void rotate(vector<int>& nums, int k) {
2.     int n = nums.size();
3.     k %= n;
4.     reverse(nums, 0, n-1);
5.     reverse(nums, 0, k-1);
6.     reverse(nums, k, n-1);
7. }
9. void reverse(vector<int>& nums, int left, int right) {
10.     while (left < right) {
11.         swap(nums[left++], nums[right--]);
12.     }
13. }

复制代码

238. 除自身以外数组的乘积

   给你一个整数数组 nums，返回 数组 answer ，其中 answer 等于 nums 中除 nums 之外别的各元素的乘积 。
  标题数据 包管 数组 nums之中恣意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
  请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。
  示例 1:

1. 输入: nums = [1,2,3,4]
2. 输出: [24,12,8,6]

复制代码

示例 2:

1. 输入: nums = [-1,1,0,-3,3]
2. 输出: [0,0,9,0,0]

复制代码

提示：
  

• 2 <= nums.length <= 10^5
  
• -30 <= nums <= 30
  
• 包管 数组 nums之中恣意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
  

  **进阶：**你可以在 O(1) 的额外空间复杂度内完成这个标题吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
  与这题724. 探求数组的中央下标类似。分别构建从前今后的乘积数组dp1，以及从后往前的乘积数组dp2，再初始化ans数组即可。

1. vector<int> productExceptSelf(vector<int>& nums) {
2.     int n = nums.size();
3.     vector<int> dp1(n + 1);
4.     dp1[0] = 1;
5.     for (int i = 1; i <= n; ++i)
6.         dp1[i] = dp1[i - 1] * nums[i - 1];
8.     vector<int> dp2(n + 2);
9.     dp2[n + 1] = 1;
10.     for (int j = n; j > 0; --j)
11.         dp2[j] = dp2[j + 1] * nums[j - 1];
13.     vector<int> ans(n);
14.     for (int i = 0; i < n; ++i)
15.         ans[i] = dp1[i] * dp2[i + 2];
16.     return ans;
17. }

复制代码

在此基础上还可以优化空间复杂度，先用ans作为从前今后的乘积数组dp1，sum作为从后往前的乘积和，再从后往前更新ans。

1. vector<int> productExceptSelf(vector<int>& nums) {
2.     int n = nums.size();
4.     vector<int> ans(n);
5.     ans[0] = 1;
6.     for (int i = 1; i < n; ++i)
7.         ans[i] = ans[i - 1] * nums[i - 1];
9.     int sum = 1;
10.     for (int i = n - 1; i >= 0; --i) {
11.         ans[i] *= sum;
12.         sum *= nums[i];
13.     }
14.     return ans;
15. }

复制代码

41. 缺失的第一个正数

   给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
  请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
  示例 1：

1. 输入：nums = [1,2,0]
2. 输出：3
3. 解释：范围 [1,2] 中的数字都在数组中。

复制代码

示例 2：

1. 输入：nums = [3,4,-1,1]
2. 输出：2
3. 解释：1 在数组中，但 2 没有。

复制代码

示例 3：

1. 输入：nums = [7,8,9,11,12]
2. 输出：1
3. 解释：最小的正数 1 没有出现。

复制代码

提示：
  

• 1 <= nums.length <= 105
  
• -231 <= nums <= 231 - 1
  

  哈希表，时间复杂度O（n），空间复杂度O（n）

1. int firstMissingPositive(vector<int>& nums) {
2.     unordered_set<int> hash;
3.     for (int num : nums) {
4.         hash.insert(num);
5.     }
6.     int ans = 1;
7.     while (1) {
8.         if (!hash.count(ans)) {
9.             return ans;
10.         }
11.         ans++;
12.     }
13.     return -1;
14. }

复制代码

置换，时间复杂度O（n），空间复杂度O（1）

1. int firstMissingPositive(vector<int>& nums) {
2.     int n = nums.size();
3.     for (int i = 0; i < n; ++i) {
4.         while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
5.             swap(nums[nums[i] - 1], nums[i]);
6.         }
7.     }
8.     for (int i = 0; i < n; ++i) {
9.         if (nums[i] != i + 1) {
10.             return i + 1;
11.         }
12.     }
13.     return n + 1;
14. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告