LeetCode——442. 数组中重复的数据

简介: LeetCode——442. 数组中重复的数据

442. 数组中重复的数据


题目描述

答案

我的答案

官方答案

方法一:将元素交换到对应的位置

方法二:使用正负号作为标记


题目描述


给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。


你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。


示例 1:

输入:nums = [4,3,2,7,8,2,3,1]

输出:[2,3]


示例 2:

输入:nums = [1,1,2]

输出:[1]


示例 3:

输入:nums = [1]

输出:[]


提示:

n == nums.length

1 <= n <= 105

1 <= nums[i] <= n

nums 中的每个元素出现 一次 或 两次


答案


我的答案


class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (!set.add(num)) {
                list.add(num);
            }
        }
        return list;
    }
}


官方答案


方法一:将元素交换到对应的位置


思路与算法


由于给定的 n 个数都在 [1,n] 的范围内,如果有数字出现了两次,就意味着 [1,n] 中有数字没有出现过。


因此,我们可以尝试将每一个数放在对应的位置。由于数组的下标范围是 [0, n-1] ,我们需要将数 ii 放在数组中下标为 i-1 的位置:


如果 i 恰好出现了一次,那么将 i 放在数组中下标为 i-1 的位置即可;

如果 i 出现了两次,那么我们希望其中的一个 i 放在数组下标中为 i-1 的位置,另一个 i 放置在任意「不冲突」的位置 j 。也就是说,数 j+1 没有在数组中出现过。

这样一来,如果我们按照上述的规则放置每一个数,那么我们只需要对数组进行一次遍历。当遍历到位置 i 时,如果nums[i]−1 !=i,说明 nums[i] 出现了两次(另一次出现在位置num[i]−1),我们就可以将 num[i] 放入答案。


放置的方法也很直观:我们对数组进行一次遍历。当遍历到位置 i 时,我们知道 nums[i] 应该被放在位置 nums[i]−1。因此我们交换 num[i] 和 nums[nums[i]−1] 即可,直到待交换的两个元素相等为止。


代码

class Solution {
    public List<Integer> 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);
            }
        }
        List<Integer> ans = new ArrayList<Integer>();
        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;
    }
}


复杂度分析


时间复杂度:O(n)。每一次交换操作会使得至少一个元素被交换到对应的正确位置,因此交换的次数为 O(n),总时间复杂度为 O(n)。


空间复杂度:O(1)。返回值不计入空间复杂度。


方法二:使用正负号作为标记


思路与算法


我们也可以给 nums[i] 加上「负号」表示数 i+1 已经出现过一次。具体地,我们首先对数组进行一次遍历。当遍历到位置 i 时,我们考虑 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 List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<Integer>();
        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;
    }
}


复杂度分析


时间复杂度:O(n)。我们只需要对数组 nums 进行一次遍历。

空间复杂度:O(1)。返回值不计入空间复杂度。

相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
57 0
|
1月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
16 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组