🎯 初学者友好指南 ‘大小为 2N 的数组中的 N 次重复元素’ – LeetCode 961 (C++ | Python | JavaScript)

Source: Dev.to

问题描述

您得到一个长度为 2N 的数组 nums。
该数组包含 N + 1 个唯一元素，其中恰好有一个元素出现 N 次。

目标： 找出并返回出现 N 次的元素。

解题思路

因为重复的元素占据了数组一半的位置，所以它的任意两个出现之间的索引距离最多为 2。
使用大小为 3 的滑动窗口扫描数组可以保证我们会遇到重复元素，除非该重复元素恰好是数组的最后一个位置。

该算法的时间复杂度为 O(N)，额外空间复杂度为 O(1)。

C++ 实现

class Solution {
public:
    int repeatedNTimes(vector& nums) {
        // Check windows of size 2 and size 3
        for (int i = 0; i + 2  int:

Python 实现

# Iterate through the list looking at neighbors
for i in range(len(nums) - 2):
    if nums[i] == nums[i + 1] or nums[i] == nums[i + 2]:
        return nums[i]

# If the repeat isn't within a distance of 2, it's the last element
return nums[-1]

JavaScript 实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function(nums) {
    // Loop through the array checking nearby elements
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] === nums[i + 1] || nums[i] === nums[i + 2]) {
            return nums[i];
        }
    }

    // Return the last element if no match was found in the loop
    return nums[nums.length - 1];
};

关键点

• 窗口策略： 只检查相邻的元素（距离 ≤ 2）就足以在 2N 数组中定位到重复元素。
• 空间效率： 该算法使用 O(1) 额外空间，远优于频率计数器需要的 O(N) 空间。
• 逻辑优于暴力： 理解元素分布背后的鸽巢原理即可得到简洁快速的解法。