961.在长度 2N 的数组中找出重复 N 次的元素：5种语言x5种方法(及其变种) —— All By Hand

【LetMeFly】961.在长度 2N 的数组中找出重复 N 次的元素：5种语言x5种方法(及其变种) —— All By Hand

力扣题目链接：https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/

给你一个整数数组 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 次

解题方法一.1：排序+看相邻

nums排个序，有且仅有出现$n$次的元素会相邻且相同。

  • 时间复杂度$O(n\log n)$
  • 空间复杂度$O(\log n)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return -1;  // FAKE RETURN
    }
};

竟然和2022.5.21写的几乎一模一样。

Python

1
2
3
4
5
6
7
8
from typing import List

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return nums[i]

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "sort"

func repeatedNTimes(nums []int) int {
    sort.Ints(nums)
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i - 1] {
            return nums[i]
        }
    }
    return -1  // FAKE RETURN
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Arrays;

class Solution {
    public int repeatedNTimes(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

Rust

1
2
3
4
5
6
7
8
9
10
11
impl Solution {
    pub fn repeated_n_times(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        for i in 1..nums.len() {
            if nums[i] == nums[i - 1] {
                return nums[i];
            }
        }
        -1  // FAKE RETURN
    }
}

解题方法一.2：排序+看中间

有一个数字恰好出现了$n$次，那么排序后中间位置的两个元素至少有一个是它。

  • 时间复杂度$O(n\log n)$
  • 空间复杂度$O(\log n)$

AC代码

C++

1
2
3
4
5
6
7
8
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int mid = nums.size() / 2;
        return nums[mid] == nums[mid + 1] ? nums[mid] : nums[mid - 1];
    }
};

C++. 不能通过版本

不能这样思考：

有一个数字恰好出现了$n$次，那么排序后要么前半段全是它要么后半段全是它。

排序后看看前两个元素相同的话就是前半段，否则就是后半段。

1
2
3
4
5
6
7
8
// THIS CANNOT BE ACCEPTED
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[0] == nums[1] ? nums[0] : nums.back();
    }
};

反例：[1, 2, 2, 3]。

Python

1
2
3
4
5
6
7
from typing import List

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        nums.sort()
        mid = len(nums) // 2
        return nums[mid] if nums[mid] == nums[mid + 1] else nums[mid - 1]

Go

1
2
3
4
5
6
7
8
9
10
11
12
package main

import "sort"

func repeatedNTimes(nums []int) int {
    sort.Ints(nums)
    mid := len(nums) / 2
    if nums[mid] == nums[mid + 1] {
        return nums[mid]
    }
    return nums[mid - 1]
}

Java

1
2
3
4
5
6
7
8
9
import java.util.Arrays;

class Solution {
    public int repeatedNTimes(int[] nums) {
        Arrays.sort(nums);
        int mid = nums.length / 2;
        return nums[mid] == nums[mid + 1] ? nums[mid] : nums[mid - 1];
    }
}

Rust

1
2
3
4
5
6
7
8
9
10
impl Solution {
    pub fn repeated_n_times(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mid: usize = nums.len() / 2;
        if nums[mid] == nums[mid + 1] {
            return nums[mid];
        }
        nums[mid - 1]
    }
}

解题方法二：哈希表

使用哈希表记录出现过的元素，如果一个元素二次出现则视为找到答案。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> visited;
        for (int t : nums) {
            if (visited.count(t)) {
                return t;
            }
            visited.insert(t);
        }
        return -1;  // FAKE RETURN
    }
};

Python

1
2
3
4
5
6
7
8
9
from typing import List

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        visited = set()
        for t in nums:
            if t in visited:
                return t
            visited.add(t)

Go

1
2
3
4
5
6
7
8
9
10
11
12
package main

func repeatedNTimes(nums []int) int {
    visited := map[int]bool{}
    for _, t := range nums {
        if _, ok := visited[t]; ok {
            return t
        }
        visited[t] = true
    }
    return -1  // FAKE RETURN
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Set;
import java.util.HashSet;

class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> visited = new HashSet<>();
        for (int t : nums) {
            if (visited.contains(t)) {
                return t;
            }
            visited.add(t);
        }
        return -1;  // FAKE RETURN
    }
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashSet;

impl Solution {
    pub fn repeated_n_times(mut nums: Vec<i32>) -> i32 {
        let mut visited = HashSet::new();
        for t in nums.iter() {
            if visited.contains(&t) {
                return *t;
            }
            visited.insert(t);
        }
        -1  // FAKE RETURN
    }
}

解题方法三：相邻相隔一次遍历

长度为$2n$的数组中一个数出现了$n$次，那么数组中这个数（假设为$t$）一定存在一下情况之一：

  1. 两个$t$相邻
  2. 两个$t$中间隔一个元素

否则，任何两个$t$之间都间隔至少两个元素，$t$的数量将会无法达到$n$。

所以我们只需要遍历一遍数组，找到相邻相同或相隔一数且相同的数就好了。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$

AC代码

C++

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];  // 前面循环中未判断nums[0]是否等于nums[1]，若前面未return则说明nums[0]=nums[1]如[1, 1, 2, 3]
    }
};

Python

1
2
3
4
5
6
7
8
from typing import List

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]

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "sort"

func repeatedNTimes(nums []int) int {
    sort.Ints(nums)
    for i := 2; i < len(nums); i++ {
        if nums[i] == nums[i-1] || nums[i] == nums[i-2] {
            return nums[i]
        }
    }
    return nums[0]
}

Java

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];
    }
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
use std::collections::HashSet;

impl Solution {
    pub fn repeated_n_times(mut nums: Vec<i32>) -> i32 {
        for i in 2..nums.len() {
            if nums[i] == nums[i - 1] || nums[i] == nums[i - 2] {
                return nums[i]
            }
        }
        nums[0]
    }
}

解题方法四：擂台赛（摩尔投票法）

假设某个元素在数组中数量占绝对优势（大于半数），那么可以数组中元素依次上擂台：

  • 如果擂台上没有人，自己成为霸主，生命值为1
  • 如果擂台上有人，且和自己相同，则霸主生命值加1
  • 如果擂台上有人，且和自己不同，则霸主生命值减1（减少至0视为死亡）

这种方法不限制其他数是否有重复，但是与本题相比本题其他数不会重复但是所寻找元素比严格大于半数少1次。

怎么办呢？将数组分为第一个数和剩下其他数两部分：

  • 如果所找元素是第一个数，那么在剩下的数组中一定存在和这个数相同的数，相同则找到
  • 如果所找元素和第一个数不相等，那么所找元素在剩下的数组中出现次数大于半数，可以使用摩尔投票法

这种方法更适合其他元素也有相同的情况 ，用在此处略有牵强。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        if (nums[0] == nums[1]) {
            return nums[0];
        }
        int now = -1, hp = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[0]) {
                return nums[0];
            }
            if (hp == 0) {
                hp = 1;
                now = nums[i];
            } else if (now == nums[i]) {
                hp++;  // 其实也可以直接return了
            } else {
                hp--;
            }
        }
        return now;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        ans, hp = -1, 0
        for t in nums[1:]:
            if t == nums[0]:
                return t
            if not hp:
                ans, hp = t, 1
            elif ans == t:
                hp += 1
            else:
                hp -= 1
        return ans

GO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main

func repeatedNTimes(nums []int) int {
    ans, hp := -1, 0
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[0] {
            return nums[0]
        }
        if hp == 0 {
            ans, hp = nums[i], 1
        } else if ans == nums[i] {
            hp++
        } else {
            hp--
        }
    }
    return ans
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int repeatedNTimes(int[] nums) {
        int ans = 0, hp = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[0]) {
                return nums[0];
            }
            if (hp == 0) {
                ans = nums[i];
                hp = 1;
            } else if (ans == nums[i]) {
                hp++;
            } else {
                hp--;
            }
        }
        return ans;
    }
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
use std::collections::HashSet;

impl Solution {
    pub fn repeated_n_times(mut nums: Vec<i32>) -> i32 {
        let mut ans: i32 = -1;
        let mut hp: i32 = 0;
        for i in 1..nums.len() {
            if nums[i] == nums[0] {
                return nums[0]
            }
            if hp == 0 {
                ans = nums[i];
                hp = 1;
            } else if ans == nums[i] {
                hp += 1;
            } else {
                hp -= 1;
            }
        }
        ans
    }
}

解题方法五(trick)：随机

每次随机选取两个元素，直到选到两个相等的元素为止。

这种方法看似很盲目，其实效率很高，所选两元素相同的概率为$\frac{n}{2n}\times \frac{n-1}{2n}\approx \frac{1}{4}$，平均4次随机选择就能找到答案，因此期望时间复杂度为$O(1)$。

为什么是$\frac{n}{2n}\times \frac{n-1}{2n}$呢？因为是全随机，第一次在$2n$个数字里面有$n$个可选，第二次还是在$2n$个数字里面有$n-1$个可选。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
private:
    inline static mt19937 gen = mt19937(random_device{}());
    inline static uniform_int_distribution<> dis;
public:
    int repeatedNTimes(vector<int>& nums) {
        dis.param(uniform_int_distribution<>::param_type(0, nums.size() - 1));
        int loc1, loc2;
        do {
            loc1 = dis(gen);
            loc2 = dis(gen);
        } while (loc1 == loc2 || nums[loc1] != nums[loc2]);
        return nums[loc1];
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
from typing import List
from random import randint

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums) - 1
        while True:
            loc1 = randint(0, n)
            loc2 = randint(0, n)
            # print(loc1, loc2)
            if loc1 != loc2 and nums[loc1] == nums[loc2]:
                return nums[loc1]

Python.TLE

注意python random.randint包含左右区间端点，而random.randrange不包含右端点，所以下面代码在[1, 2, 3, 3]这种时候会因为永远无法随机到3而超时：

1
2
3
4
5
6
7
8
9
10
11
12
from typing import List
from random import randrange

# THIS CANNOT ACCESS
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums) - 1
        while True:
            loc1 = randrange(0, n)
            loc2 = randrange(0, n)
            if loc1 != loc2 and nums[loc1] == nums[loc2]:
                return nums[loc1]

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

import "math/rand"

func repeatedNTimes(nums []int) int {
    n := len(nums)
    for true {
        l1 := rand.Intn(n)
        l2 := rand.Intn(n)
        if l1 != l2 && nums[l1] == nums[l2] {
            return nums[l1]
        }
    }
    return -1  // FAKE RETURN
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Random;

class Solution {
    public int repeatedNTimes(int[] nums) {
        Random random = new Random();
        int n = nums.length;
        while (true) {
            int l1 = random.nextInt(n);
            int l2 = random.nextInt(n);
            if (l1 != l2 && nums[l1] == nums[l2]) {
                return nums[l1];
            }
        }
    }
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
use rand::Rng;

impl Solution {
    pub fn repeated_n_times(mut nums: Vec<i32>) -> i32 {
        let mut rng = rand::thread_rng();  // 一定要为mut
        let n= nums.len();
        loop {
            let l1 = rng.gen_range(0..n);
            let l2 = rng.gen_range(0..n);
            if l1 != l2 && nums[l1] == nums[l2] {
                return nums[l1];
            }
        }
    }
}

End

The Real End, Thanks!

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

题解 > LeetCode
#题解 #简单 #数组 #LeetCode #哈希表
961.在长度 2N 的数组中找出重复 N 次的元素：5种语言x5种方法(及其变种) —— All By Hand
https://blog.letmefly.xyz/2026/01/02/LeetCode 0961.在长度2N的数组中找出重复N次的元素/
作者
发布于
2026年1月2日
许可协议