网站建设分为多少模块,wordpress登录微信插件下载,设计素材免费下载网站,如何宣传推广自己的产品一.题目要求
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
二.题目难度
困难
三.输入样例
示例 1#xff1a; 输入#xff1a;nums [1,2,0] 输出#xff1a;3…一.题目要求
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
二.题目难度
困难
三.输入样例
示例 1 输入nums [1,2,0] 输出3 解释范围 [1,2] 中的数字都在数组中。
示例 2 输入nums [3,4,-1,1] 输出2 解释1 在数组中但 2 没有。
示例 3 输入nums [7,8,9,11,12] 输出1 解释最小的正数 1 没有出现。
提示 1 nums.length 105 -231 nums[i] 231 - 1
四.解题思路
原地哈希 思路长度为n的数组nums缺失的第一个正数的范围只可能是1 ~ n1 极端情况长度为5 数组nums为 1, 2, 3, 4, 5 即前五个数都出现那么缺失的数就是n 1 6 遍历一遍数组将nums[i]的值映射到原本属于它的位置上此题的映射规则为 对于数 val 映射到 nums[val - 1] 如nums[5] 4 此时值4处在了值6应该在的位置要把4映射到nums[3] 以此类推把所有符合1 - n的数都映射到其对应的位置那么在nums[i]中某个数不是i1则这个数就是所求缺失值 否则表面所有数都是按照1234的顺序映射 那么不存在的最小整数就是n 1
五.代码实现
class Solution {
public:int firstMissingPositive(vectorint nums) {int n nums.size();for (int i 0; i n; i) {// 注意:// 这里while的目的是让nums[i]里的元素被最终定下来,最后留在nums[i]的元素一定要么是i 1要么是一个不符合1 ~ n的数while (nums[i] 0 nums[i] n nums[i] ! i 1 nums[nums[i] - 1] ! nums[i]) {std::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;}
};六.题目总结
原地哈希技巧的应用
