长沙网站开发的网站,国家职业资格证书网站,怎样用阿里云建设网站,广告经营许可证错误的集合 题目描述优化空间代码演示 题目描述 难度 - 简单 LC645 - 错误的集合 集合 s 包含从 1 到 n 的整数。不幸的是#xff0c;因为数据错误#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值#xff0c;导致集合 丢失了一个数字 并且 有一个数… 错误的集合 题目描述优化空间代码演示 题目描述 难度 - 简单 LC645 - 错误的集合 集合 s 包含从 1 到 n 的整数。不幸的是因为数据错误导致集合里面某一个数字复制了成了集合里面的另外一个数字的值导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了集合 S 发生错误后的结果。 请你找出重复出现的整数再找到丢失的整数将它们以数组的形式返回。 示例 1 输入nums [1,2,2,4] 输出[2,3] 示例 2 输入nums [1,1] 输出[1,2] 提示 2 nums.length 104 1 nums[i] 104 优化空间 如果用hashMap 去记录每个数字出现的频率那就是简单的程度但既然写出来这个题就不会用hashMap,我们用原数组的基础上实现这个功能。优化了空间复杂度。 这个问题的特点是每个元素和数组索引有一定的对应关系。 我们现在自己改造下问题暂且将nums中的元素变为[0…N-1]这样每个元素就和一个数组索引完全对应了这样方便理解一些。 如果说nums中不存在重复元素和缺失元素那么每个元素就和唯一一个索引值对应对吧 现在的问题是有一个元素重复了同时导致一个元素缺失了这会产生什么现象呢会导致有两个元素对应到了同一个索引而且会有一个索引没有元素对应过去。 那么如果我能够通过某些方法找到这个重复对应的索引不就是找到了那个重复元素么找到那个没有元素对应的索引不就是找到了那个缺失的元素了么 那么如何不使用额外空间判断某个索引有多少个元素对应呢这就是这个问题的精妙之处了 通过将每个索引对应的元素变成负数以表示这个索引被对应过一次了. 代码演示
class Solution {public int[] findErrorNums(int[] nums) {int cop -1;for(int i 0; i nums.length;i){int index Math.abs(nums[i]) - 1;if(nums[index] 0){cop Math.abs(nums[i]);}else{nums[index] * -1;}}int miss -1;for(int i 0; i nums.length;i){if(nums[i] 0){miss i 1;}}return new int[]{cop,miss};}
}
