배열에서 두 번 발생하지 않는 유일한 숫자를 찾는 방법

배열에서 두 번 발생하지 않는 유일한 숫자를 찾는 방법

---

이 질문에 이미 답변이 있습니다.

• 배열에서 짝을 이루지 않는 유일한 요소 찾기 9 답변

다음은 면접에서 가져온 것입니다.

정수를 포함하는 주어진 배열에서 각 숫자는 반복되지 않는 하나를 제외하고는 한 번 반복됩니다. 반복되지 않는 숫자를 찾는 함수를 작성하세요.

HashSet 사용에 대해 생각했지만 모든 것이 복잡해질 수 있습니다.

간단한 솔루션에 대한 아이디어가 있습니까?

---

0으로 초기화 된 정수 "결과"를 정의한 다음 배열의 모든 요소에 XOR 논리를 적용하여 비트 연산을 수행 할 수 있습니다.

결국 "결과"는 한 번만 나타나는 유일한 요소와 동일합니다.

result = 0
for i in array:
  result ^= i
return result

http://en.wikipedia.org/wiki/Bitwise_operation#XOR

예를 들어 배열에 [3, 4, 5, 3, 4] 요소가 포함 된 경우 알고리즘은 다음을 반환합니다.

3 ^ 4 ^ 5 ^ 3 ^ 4

그러나 XOR 연산자 ^는 연관적이고 교환 적이므로 결과는 다음과 같습니다.

(3 ^ 3) ^ (4 ^ 4) ^ 5

모든 정수 i에 대해 i ^ i = 0이고 i ^ 0 = i이므로

(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5

---

이 질문을 전에 본 적이 있습니다. 속임수입니다. 반복되는 모든 숫자가 정확히 두 번 나타난다 고 가정하면 다음과 같이합니다.

int result = 0;
for (int a : arr)
    result ^= a;

---

또 다른 "일반적인"솔루션 (Java) :

public static int findSingle(int[] array) {

    Set<Integer> set = new HashSet<Integer>();

    for (int item : array) {
        if (!set.remove(item)) {
            set.add(item);
        }
    }       

    assert set.size() == 1;

    return set.iterator().next();
}

제 생각에는 XOR의 솔루션이 아름답습니다.

이것은 XOR만큼 빠르지는 않지만 HashSet을 사용하면 O (n)에 가깝습니다. 그리고 확실히 더 읽기 쉽습니다.

---

가장 좋은 대답은 이미 주어졌습니다 (요소를 XOR-ing). 이것은 대안적이고보다 일반적인 방법을 제공하는 것입니다.

입력 배열이 정렬되면 (정렬 할 수 있음) 쌍으로 요소를 반복 (2 단계 씩) 할 수 있고 "쌍"의 요소가 다른 경우 완료됩니다.

public static int findSingle(int[] arr) {
    Arrays.sort(arr);
    for (int i = 0, max = arr.length - 1; i < max; i += 2)
        if (arr[i] != arr[i + 1])
            return arr[i];
    return arr[arr.length - 1]; // Single element is the last
}

참고 : 이 솔루션은 입력 배열을 정렬합니다. 원치 않거나 허용되지 않는 경우 먼저 복제 할 수 있습니다.

arr = arr.clone();

입력 배열이 정렬되면 물론 Arrays.sort(arr)호출을 생략 할 수 있습니다.

일반화

이 솔루션의 장점은 비교할 수 있고 정렬 할 수있는 모든 유형 (을 구현하는 유형)에 적용 할 수 있다는 것입니다 ( Comparable예 : String또는) Date. XOR솔루션은 숫자로 제한됩니다.

다음은 비교 가능한 모든 요소 유형의 입력 배열을 취하는 약간 수정 된 버전입니다.

public static <E extends Comparable<E>> E findSingle(E[] arr) {
    Arrays.sort(arr);
    for (int i = 0, max = arr.length - 1; i < max; i += 2)
        if (arr[i].compareTo(arr[i + 1]) != 0)
            return arr[i];
    return arr[arr.length - 1]; // Single element is the last
}

Note: In most cases you could also use arr[i].equals(arr[i + 1]) to compare elements instead of using Comparable.compareTo(). For details read the linked javadoc. Quoting the relevant part:

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

Now you can call this with a String[] for example:

System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));

Output:

2

Final notes:

Starting from the problem statement it is not checked whether there are more than 2 occurrences of the elements, and neither is whether the array length is odd. Also the second example doesn't check for null values, these are to be added if necessary.

---

Here's a slightly less obfuscated way to do it:

List list = Arrays.asList(a);
int result;
for(int i:a)
{
    if(list.indexOf(i)==list.lastIndexOf(i))
    {
        result = i;
        break;
    }
}

result will contain the non-repeated value.

ReferenceURL : https://stackoverflow.com/questions/29333689/how-to-find-the-only-number-in-an-array-that-doesnt-occur-twice