济南品牌网站建设,wordpress怎么调用简码,查询公司水利平台网站,洛可可设计公司总部输入#xff1a;一个没有排序的正数数组nums 输出#xff1a;在 nums数组中未出现的最小的正整数 规则#xff1a;数组中的元素可能是负数#xff0c;也可能重复。要求时间复杂度O(n)#xff0c;空间复杂度O(1)。 分析#xff1a;题目其实很简单#xff0c;遍历一次放入…输入一个没有排序的正数数组nums 输出在 nums数组中未出现的最小的正整数 规则数组中的元素可能是负数也可能重复。要求时间复杂度O(n)空间复杂度O(1)。 分析题目其实很简单遍历一次放入map中。然后从1到n遍历是否在map中存在。但是这样不符合空间复杂度。 分析2力扣官方解答。首先我们不需要考虑负数、0以及大于n1的值。因为答案一定在[1,n1]之间。因为空间限制条件我们可以使用原数组实现一个map类似布隆过滤器。我们假设修改之后nums[i]0表示i1存在否则i1不存在。 具体实现算法是 1 检查数组中1是否存在。不存在则返回1否则进入2. 2 将数组中不在[1,n]之间的值都设置为1。 3 遍历数组设置nums[nums[i] -1] 负数这里需要注意元素值可能重复。 4 遍历数组找到第一个nums[i]0的元素返回。
说明代码实现一些细节和算法过程略有不同。
public int firstMissingPositive(int[] nums) {int n nums.length;//检查1是否缺失int oneCount 0;for(int num : nums){if(num1){oneCount 1 ;break;}}if(oneCount 0) return 1;if(n 1) return 2;//替换无效数字为1for(int i0; i n; i){if(nums[i] 0 || nums[i]n){nums[i] 1;}}//一个布隆过滤器 nums[i] 0表示 i不存在nums[i]0表示i存在。nums[0]代表n是否存在。 for(int i0;i n; i){int a Math.abs(nums[i]);if(a n){nums[0] - Math.abs(nums[0]);}else{nums[a] -Math.abs(nums[a]);}}for(int i1;i n; i){if(nums[i] 0){return i;}}return nums[0] 0? n: n1;}分析3其实也是用nums[i]的值表示i1是不是存在。这里的判断依据是如果nums[i]i1则说明i1存在否则不存在。这个方法实现的技巧是交换。上一个方法实现的技巧是替换。原链接。 public int firstMissingPositive(int[] nums) {int n nums.length;for(int i0;i n; i){while(nums[i] 0 nums[i]n nums[nums[i] -1 ]!nums[i]){swap(nums,i,nums[i]-1);}}for(int i0;i n; i){if(nums[i] ! i1){return i1;}}return n1;}private void swap(int[] nums, int i, int j) {int tmp nums[i] ;nums[i] nums[j];nums[j] tmp;}
