学校网站建设要求,沈阳网页设计公司排名,推广app的营销策略,网站建设佰首选金手指十八文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
哈希表
二【题目难度】
困难
三【题目编号】
41.缺失的第一个正数
四【题目描述】
给你一个… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
哈希表
二【题目难度】
困难
三【题目编号】
41.缺失的第一个正数
四【题目描述】
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
五【题目示例】 示例 1 输入nums [1,2,0]输出3 示例 2 输入nums [3,4,-1,1]输出2 示例 3 输入nums [7,8,9,11,12]输出1
六【题目提示】 1 n u m s . l e n g t h 5 ∗ 1 0 5 1 nums.length 5 * 10^5 1nums.length5∗105 − 2 31 n u m s [ i ] 2 31 − 1 -2^{31} nums[i] 2^{31} - 1 −231nums[i]231−1
七【解题思路】
对数组中的元素进行“原地哈希”第i个元素映射到i-1的位置这样对于1-N中的元素如果没有空缺那么缺失的第一个正数一定是N1如果有空缺那么缺失的第一个整数一定在1-N中然后我们遍历数组对于映射不匹配的元素直接返回即可
八【时间频度】
时间复杂度 O ( n ) O(n) O(n) n n n为传入的数组的长度空间复杂度 O ( 1 ) O(1) O(1)
九【代码实现】
Java语言版
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for(int i 0;i n;i){while(0 nums[i] nums[i] n nums[nums[i] - 1] ! nums[i]){swap(nums, nums[i] - 1, i);}}for(int i 0;i n;i){if(nums[i] ! i 1){return i 1;}}return n 1;}public void swap(int[] nums, int index1, int index2){int temp nums[index1];nums[index1] nums[index2];nums[index2] temp;}
}C语言版
void swap(int* nums, int index1, int index2)
{int temp nums[index1];nums[index1] nums[index2];nums[index2] temp;
}int firstMissingPositive(int* nums, int numsSize)
{int n numsSize;for(int i 0;i n;i){while(0 nums[i] nums[i] n nums[nums[i] - 1] ! nums[i]){swap(nums, nums[i] - 1, i);}}for(int i 0;i n;i){if(i 1 ! nums[i]){return i 1;}}return n 1;
}Python语言版
class Solution:def firstMissingPositive(self, nums: List[int]) - int:n len(nums)for i in range(0, n):while 1 nums[i] and nums[i] n and nums[nums[i] - 1] ! nums[i]:self.swap(nums, nums[i] - 1, i)for i in range(0, n):if nums[i] ! i 1:return i 1return n 1def swap(self, nums, index1, index2):temp nums[index1]nums[index1] nums[index2]nums[index2] tempC语言版
class Solution {
public:int firstMissingPositive(vectorint nums) {int n nums.size();for(int i 0;i n;i){while(0 nums[i] nums[i] n nums[nums[i] - 1] ! nums[i]){swap(nums, nums[i] - 1, i);}}for(int i 0;i n;i){if(nums[i] ! i 1){return i 1;}}return n 1;}void swap(vectorint nums, int index1, int index2){int temp nums[index1];nums[index1] nums[index2];nums[index2] temp;}
};十【提交结果】 Java语言版 C语言版 Python语言版 C语言版
