🎯 초보자용 가이드 'N-Repeated Element in Size 2N Array' – LeetCode 961 (C++ | Python | JavaScript)

Source: Dev.to

Problem Description

길이가 2N인 배열 nums가 주어집니다.
배열에는 N + 1개의 고유한 요소가 있으며, 그 중 정확히 하나의 요소가 N번 나타납니다.

목표: N번 반복되는 요소를 찾아 반환합니다.

Solution Overview

반복되는 요소가 배열 절반을 차지하므로, 두 번 나타나는 위치는 최대 두 인덱스 차이가 됩니다.
크기 3의 슬라이딩 윈도우로 배열을 스캔하면, 마지막 배열 원소인 경우를 제외하고는 중복을 반드시 만나게 됩니다.

알고리즘은 O(N) 시간에 실행되고 O(1) 추가 공간을 사용합니다.

C++ Implementation

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

Python Implementation

# 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 Implementation

/**
 * @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];
};

Key Insights

• Window Strategy: 인접한 이웃(거리 ≤ 2)만 확인하면 2N 배열에서 반복되는 요소를 찾기에 충분합니다.
• Space Efficiency: 알고리즘은 O(1) 추가 공간을 사용하며, 빈도 카운터가 필요로 하는 O(N) 공간보다 훨씬 효율적입니다.
• Logic Over Brute Force: 요소 분포에 대한 비둘기집 원리를 이해하면 간단하고 빠른 해결책을 얻을 수 있습니다.