961. N-Repeated Element in Size 2N Array

leetcode easy

#array#csharp#easy#leetcode

Task

Вам дан целочисленный массив nums со следующими свойствами:

nums.length == 2 * n.

nums содержит n + 1 уникальных элементов.

Ровно один элемент массива nums повторяется n раз.

Верните элемент, который повторяется n раз.

Пример:

Input: nums = [1,2,3,3]

Output: 3

C# solution

matched/original

public class Solution {
    public int RepeatedNTimes(int[] A) {
        for (int k = 1; k <= 3; ++k) {
            for (int i = 0; i < A.Length - k; ++i) {
                if (A[i] == A[i + k]) {
                    return A[i];
                }
            }
        }
        throw new InvalidOperationException("No solution found");
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int RepeatedNTimes(vector<int>& A) {
        for (int k = 1; k <= 3; ++k) {
            for (int i = 0; i < A.size() - k; ++i) {
                if (A[i] == A[i + k]) {
                    return A[i];
                }
            }
        }
        throw new InvalidOperationException("No solution found");
    }
}

Java solution

matched/original

class Solution {
    public int repeatedNTimes(int[] A) {
        for (int k = 1; k <= 3; ++k)
            for (int i = 0; i < A.length - k; ++i)
                if (A[i] == A[i+k])
                    return A[i];

        throw null;
    }
}

Go solution

matched/original

func repeatedNTimes(A []int) int {
    for k := 1; k <= 3; k++ {
        for i := 0; i < len(A) - k; i++ {
            if A[i] == A[i + k] {
                return A[i]
            }
        }
    }
    return -1
}

Explanation

Algorithm

Проверить все подмассивы длиной 4. В таком подмассиве обязательно будет главный элемент, повторяющийся n раз.

Сравнить элементы массива с их соседями на расстоянии 1, 2 и 3. Если найдется повторяющийся элемент, он и будет искомым.

Вернуть найденный элемент.

😎