N-повторный элемент в массиве размера 2N

Question

В массиве A размером 2N имеется N+1 уникальных элементов, и ровно один из этих элементов повторяется N раз.

Возвращает элемент, повторенный N раз.

Я пытаюсь решить этот алгоритм, но не могу понять, почему мой счет продолжает сбрасываться.Любые входные данные действительно будут оценены.

public class RepeatedElementInSize2NArray {

    public static void main(String[] args) {
        int[] inputArr = new int[] {1,2,3,3};
        int repeatedElement = findRepeatedElement(inputArr);
        System.out.println("Repeated element : "+repeatedElement);

    }

    public static int findRepeatedElement(int[] inputArr) {
        Map<Integer, Integer> repeatedElementMap = new HashMap<Integer, Integer>();
        int count = 0;
        for (int i = 0; i < inputArr.length; i++) {
            if (repeatedElementMap.containsKey(inputArr[i])) {
                count = repeatedElementMap.get(inputArr[i]);
                repeatedElementMap.put(inputArr[i], count++);
            } else {
                repeatedElementMap.put(inputArr[i], 1);
            }
        }
        int length = inputArr.length;
        int repeatedElement = 0;
        if (repeatedElementMap.containsValue(length % 2)) {
            repeatedElement = repeatedElementMap.get(length % 2);
        }
        return repeatedElement;

    }

}

Answer 1

Проблема в строке repeatedElementMap.put(inputArr[i], count++);

Выражение count++ будет увеличивать значение count, но возвращает старое значение count .

Таким образом, код repeatedElementMap.put(inputArr[i], count++); также можно записать так:

repeatedElementMap.put(inputArr[i], count);
count += 1;

Эффект будет таким же, но во втором коде вы четко видите, что есть проблема.

Решение

Заменить строку следующим образом: repeatedElementMap.put(inputArr[i], count + 1);

Редактировать

Как и в Azurefrog, упомянутой в комментариях, при поиске повторяющегося элемента есть еще одна проблема:

В последнем операторе if вы ищете содержащее значение, и если значение найдено, вы пытаетесь получить элемент. Но метод get ищет ключ, а не значение. Кроме того, я не совсем понимаю, почему вы используете модуль 2 вместо простого деления на 2. Лучшим способом было бы просто просмотреть записи и найти тот, который имеет искомое количество элементов, например:

for (Map.Entry<Integer, Integer> entry : repeatedElementMap.entrySet()) {
    if (entry.getValue() == length / 2) {
        repeatedElement = entry.getKey();
    }
}

Таким образом, полный рабочий код будет выглядеть так:

import java.util.HashMap;
import java.util.Map;

public class test {

    public static void main(String[] args) {
        int[] inputArr = new int[] {1, 2, 3, 3};
        int repeatedElement = findRepeatedElement(inputArr);
        System.out.println("Repeated element : " + repeatedElement);

    }

    public static int findRepeatedElement(int[] inputArr) {
        Map<Integer, Integer> repeatedElementMap = new HashMap<Integer, Integer>();
        int count = 0;
        for (int i = 0; i < inputArr.length; i++) {
            if (repeatedElementMap.containsKey(inputArr[i])) {
                count = repeatedElementMap.get(inputArr[i]);
                repeatedElementMap.put(inputArr[i], count+1);
            }
            else {
                repeatedElementMap.put(inputArr[i], 1);
            }
        }
        int length = inputArr.length;
        int repeatedElement = 0;

        for (Map.Entry<Integer, Integer> entry : repeatedElementMap.entrySet()) {
            if (entry.getValue() == length / 2) {
                repeatedElement = entry.getKey();
            }
        }

        return repeatedElement;
    }
}

Answer 2

Это должно быть ++count вместо count++ в строке repeatedElementMap.put(inputArr[i], count++); Причина в том, что последний сначала возвращает значение count перед увеличением значения, тогда как первый увеличивает значение сначала, а затем возвращает его.

Answer 3

count++ - это постинкремент, то есть значение, которое вы вставляете в хэш-карту, равно значению count, а затем count увеличивается.

++count - это предварительное приращение,Значение, которое вы вставляете в хэш-карту, равно count + 1, поскольку count заранее увеличивается.

Конечно, в этом случае вам необходимо предварительное увеличение.Ваша проблема в том, что вы никогда не вставляете в хэш-карту значение, большее значения 1 от первоначальной вставки, поскольку вы делаете постинкремент.

Но, честно говоря, вообще не нужно обновлять countтак как это просто временная переменная для значения в хэш-карте.Вместо этого было бы яснее просто иметь

repeatedElementMap.put(inputArr[i], count + 1);