【字节三面】41. 缺失的第一个正数

41. 缺失的第一个正数

解题思路

• 在原数组上进行操作 如果数字是2 将其放在索引为1的位置上
• 数字x 放在索引为x - 1的位置上
• 对于长度为n的数组 其中没有出现的最小正整数只能在[1,n + 1]
• 引入如果1 - n 这些数都出现了 那么答案就是n + 1
• 如果都没有出现完全 那么答案就在[1,n]中没有出现最小正整数

class Solution {public int firstMissingPositive(int[] nums) {// 字节三面  // 在原数组上进行操作 如果数字是2 将其放在索引为1的位置上// 数字x 放在索引为x - 1的位置上// 对于长度为n的数组 其中没有出现的最小正整数只能在[1,n + 1] // 引入如果1 - n 这些数都出现了 那么答案就是n + 1 // 如果都没有出现完全  那么答案就在[1,n]中没有出现最小正整数for(int i = 0; i < nums.length; i++){// 一个萝卜一个坑while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]){check(nums, i, nums[i] - 1);// 交换操作}}  //  找到第一个不匹配的位置for(int i = 0; i < nums.length; i++){if(nums[i] != i + 1){return i + 1;}} return nums.length + 1;}public void check(int[] nums, int index1, int index2) {// 互换位置int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}