福建省建设厅网站 登录,oppo手机应用商店,有哪些网站可以做ppt,做视频赚钱的网站给你一个长度为 n 的整数数组 nums #xff0c;其中 nums 的所有整数都在范围 [1, n] 内#xff0c;且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数#xff0c;并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问…给你一个长度为 n 的整数数组 nums 其中 nums 的所有整数都在范围 [1, n] 内且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
class Solution {public ListInteger findDuplicates(int[] nums) {//思路遍历数组每个数-1再取模找出真实位置再加上数组的长度放进数组真实的位置上//再遍历发现数组中元素大于2倍数组长度时将其下标1添加进返回结果的数组int len nums.length;for(int num : nums){//找出真实位置int x (num - 1) % len;//加上数组长度nums[x] len; }//创建返回结果的数组ListInteger ret new ArrayListInteger();//遍历数组找出数组中元素大于2倍数组长度的值for(int i 0;i len;i){if(nums[i] len * 2){ret.add(i1);}}return ret;}
} 官解 方法一将元素交换到对应的位置 思路与算法 由于给定的 n个数都在 [1,n]的范围内如果有数字出现了两次就意味着 [1,n] 中有数字没有出现过。 因此我们可以尝试将每一个数放在对应的位置。由于数组的下标范围是 [0,n−1]我们需要将数 i 放在数组中下标为 i−1 的位置 如果 i 恰好出现了一次那么将 iii 放在数组中下标为 i−1 的位置即可 如果 i 出现了两次那么我们希望其中的一个 i 放在数组下标中为 i−1 的位置另一个 i 放置在任意「不冲突」的位置 j。也就是说数 j1 没有在数组中出现过。 这样一来如果我们按照上述的规则放置每一个数那么我们只需要对数组进行一次遍历。当遍历到位置 i时如果 nums[i]−1≠i说明 nums[i]出现了两次另一次出现在位置 num[i]−1我们就可以将 num[i]\textit{num}[i]num[i] 放入答案。 放置的方法也很直观我们对数组进行一次遍历。当遍历到位置 iii 时我们知道 nums[i]应该被放在位置 nums[i]−1。因此我们交换 num[i]和 nums[nums[i]−1] 即可直到待交换的两个元素相等为止。 class Solution {public ListInteger findDuplicates(int[] nums) {int n nums.length;for (int i 0; i n; i) {while (nums[i] ! nums[nums[i] - 1]) {swap(nums, i, nums[i] - 1);}}ListInteger ans new ArrayListInteger();for (int i 0; i n; i) {if (nums[i] - 1 ! i) {ans.add(nums[i]);}}return ans;}public void swap(int[] nums, int index1, int index2) {int temp nums[index1];nums[index1] nums[index2];nums[index2] temp;}
} 方法二使用正负号作为标记 思路与算法 我们也可以给 nums[i]加上「负号」表示数 i1已经出现过一次。具体地我们首先对数组进行一次遍历。当遍历到位置 iii 时我们考虑 nums[nums[i]−1]的正负性 如果 nums[nums[i]−1] 是正数说明 nums[i]还没有出现过我们将 nums[nums[i]−1] 加上负号 如果 nums[nums[i]−1]是负数说明 nums[i]已经出现过一次我们将 nums[i]放入答案。 细节 由于 nums[i] 本身可能已经为负数因此在将nums[i] 作为下标或者放入答案时需要取绝对值。 class Solution {public ListInteger findDuplicates(int[] nums) {int n nums.length;ListInteger ans new ArrayListInteger();for (int i 0; i n; i) {int x Math.abs(nums[i]);if (nums[x - 1] 0) {nums[x - 1] -nums[x - 1];} else {ans.add(x);}}return ans;}
}
