LC 0961.N-Repeated Element in Size 2N Array

题目描述

这是 LeetCode 上的 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 次

解答

方法一：哈希表

最简单的方法就是建立一个哈希表，每次遇到没有加入的计数，如果遇到重复的就返回该字母。

class Solution {
    public int repeatedNTimes(int[] nums) {
        var hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length / 2 + 2; ++i) {
            if (hash.containsKey(nums[i])) {
                return nums[i];
            }
            hash.put(nums[i], 1);
        }
        return -1;
    }
}

• 时间复杂度：\(O(N)\)，其中 N 为 nums 的长度，最坏情况下要遍历 N + 2 个元素才能找到。

• 空间复杂度：\(O(N)\)，其中 N 为 nums 的长度，最坏情况下要建立的哈希键值对为 N + 1。

方法二：数学

@Source:题解来源

我们可以考虑重复的元素 x 在数组 nums 中出现的位置。

如果相邻的 x 之间至少都隔了 2 个位置，那么数组的总长度至少为： \[ n + 2 (n - 1) = 3n - 2 \]

当 n > 2 时，3n − 2 > 2n，不存在满足要求的数组。因此一定存在两个相邻的 x，它们的位置是连续的，或者只隔了 1 个位置。

当 n = 2 时，数组的长度最多为 2n = 4，因此最多只能隔 2 个位置。

这样一来，我们只需要遍历所有间隔 2 个位置及以内的下标对，判断对应的元素是否相等即可。

class Solution {
    public int repeatedNTimes(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int t = nums[i];
            if ((i >= 1 && nums[i - 1] == t) ||
            (i >= 2 && nums[i - 2] == t) || 
            (i >= 3 && nums[i - 3] == t)) {
                return t;
            }
        }
        return -1;
    }
}

• 时间复杂度：\(O(N)\)，最多对数组进行三次遍历（除了 n = 2之外，最多遍历两次）。

• 空间复杂度：\(O(1)\)。

每题一图