跳转至

961. 在长度 2N 的数组中找出重复 N 次的元素

题目描述

给你一个整数数组 nums ，该数组具有以下属性：

  • nums.length == 2 * n.
  • nums 包含 n + 1 个 不同的 元素
  • nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

 

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

输入：nums = [2,1,2,5,3,2]
输出：2

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

 

提示：

  • 2 <= n <= 5000
  • nums.length == 2 * n
  • 0 <= nums[i] <= 104
  • nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

解法

方法一：哈希表

由于数组 \(\textit{nums}\) 一共有 \(2n\) 个元素，其中有 \(n + 1\) 个不同的元素，且有一个元素重复了 \(n\) 次，说明数组中的其余 \(n\) 个元素都是不同的。

因此，我们只需要遍历数组 \(\textit{nums}\)，用哈希表 \(s\) 记录遍历过的元素。当遍历到某个元素 \(x\) 时，如果 \(x\) 在哈希表 \(s\) 中已经存在，说明 \(x\) 是重复的元素，直接返回 \(x\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

1
2
3
4
5
6
7
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        s = set()
        for x in nums:
            if x in s:
                return x
            s.add(x)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> s = new HashSet<>(nums.length / 2 + 1);
        for (int i = 0;; ++i) {
            if (!s.add(nums[i])) {
                return nums[i];
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0;; ++i) {
            if (s.count(nums[i])) {
                return nums[i];
            }
            s.insert(nums[i]);
        }
    }
};

1
2
3
4
5
6
7
8
9
func repeatedNTimes(nums []int) int {
    s := map[int]bool{}
    for i := 0; ; i++ {
        if s[nums[i]] {
            return nums[i]
        }
        s[nums[i]] = true
    }
}

1
2
3
4
5
6
7
8
9
function repeatedNTimes(nums: number[]): number {
    const s: Set<number> = new Set();
    for (const x of nums) {
        if (s.has(x)) {
            return x;
        }
        s.add(x);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
    const s = new Set();
    for (const x of nums) {
        if (s.has(x)) {
            return x;
        }
        s.add(x);
    }
};

方法二：数学

根据题目描述，数组 \(\textit{nums}\) 中有一半的元素都是相同的，如果我们将数组视为环形排列，那么两个相同元素之间的最多间隔 \(1\) 个其他元素。

因此，我们从下标 \(2\) 开始遍历数组 \(\textit{nums}\)，对于每个下标 \(i\)，我们比较 \(\textit{nums}[i]\) 与 \(\textit{nums}[i - 1]\) 和 \(\textit{nums}[i - 2]\) 的值，如果相等则返回该值。

如果没有在上述过程中找到重复的元素，那么重复的元素一定是 \(\textit{nums}[0]\)，我们直接返回 \(\textit{nums}[0]\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(\textit{nums}\) 的长度。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for i in range(2, len(nums)):
            if nums[i] == nums[i - 1] or nums[i] == nums[i - 2]:
                return nums[i]
        return nums[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int repeatedNTimes(int[] nums) {
        for (int i = 2; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1] || nums[i] == nums[i - 2]) {
                return nums[i];
            }
        }
        return nums[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        for (int i = 2; i < nums.size(); ++i) {
            if (nums[i] == nums[i - 1] || nums[i] == nums[i - 2]) {
                return nums[i];
            }
        }
        return nums[0];
    }
};

1
2
3
4
5
6
7
8
func repeatedNTimes(nums []int) int {
    for i := 2; i < len(nums); i++ {
        if nums[i] == nums[i-1] || nums[i] == nums[i-2] {
            return nums[i]
        }
    }
    return nums[0]
}

1
2
3
4
5
6
7
8
function repeatedNTimes(nums: number[]): number {
    for (let i = 2; i < nums.length; ++i) {
        if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) {
            return nums[i];
        }
    }
    return nums[0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
    for (let i = 2; i < nums.length; ++i) {
        if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) {
            return nums[i];
        }
    }
    return nums[0];
};

评论