We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
出处:LeetCode 算法第40题 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1 说明: 你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
出处:LeetCode 算法第40题
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3
示例 2:
输入: [3,4,-1,1] 输出: 2
示例 3:
输入: [7,8,9,11,12] 输出: 1
说明:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
本题的难点在于时间复杂度为O(n),而空间复杂度为常数,这就限制了我们只能使用原数组进行操作。所以我们可以使用下标为i的项保存i+1来解决,如果其中第i项的值不等于i+1,则说明数组中没有i+1这个正数。
var firstMissingPositive = function (nums) { var len = nums.length; if (len <= 0) { return 1; } for (var i = 0; i < len; i++) { if (nums[i] > 0) { while(nums[i] < i + 1 && nums[i] != nums[nums[i] -1]) { var tempIndex = nums[i] - 1; var temp = nums[i]; nums[i] = nums[tempIndex]; nums[tempIndex] = temp; } } } for (var i = 0; i < len; i++) { if (nums[i] !== i + 1) { return i + 1; } } return nums.length + 1; };
The text was updated successfully, but these errors were encountered:
No branches or pull requests
题目
思路
本题的难点在于时间复杂度为O(n),而空间复杂度为常数,这就限制了我们只能使用原数组进行操作。所以我们可以使用下标为i的项保存i+1来解决,如果其中第i项的值不等于i+1,则说明数组中没有i+1这个正数。
解答
The text was updated successfully, but these errors were encountered: