두 배열 사이에서 고유 한 요소를 찾는 더 빠른 알고리즘?

두 배열 사이에서 고유 한 요소를 찾는 더 빠른 알고리즘?

---

편집 :이 질문에 새로운 사람을 위해 무슨 일이 일어 났는지 명확히하는 답변을 게시했습니다. 수락 된 답변은 원래 게시 된 내 질문에 가장 적합한 답변이지만 자세한 내용은 내 답변을 참조하십시오.

참고 :이 문제는 원래 의사 코드였으며 목록을 사용했습니다. Java 및 배열에 적용했습니다. 따라서 Java 관련 트릭 (또는 해당 문제에 대한 모든 언어의 트릭)을 사용하는 솔루션을보고 싶지만 원래 문제는 언어 독립적이라는 점을 기억하십시오.

문제

두 개의 정렬되지 않은 정수 배열이 a있고 b요소 반복이 허용 된다고 가정 해 보겠습니다 . 배열 중 하나에 추가 요소가 있다는 점을 제외하면 ( 포함 된 요소와 관련하여) 동일 합니다. 예로서:

int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};

이 두 배열을 입력으로 받아 단일 고유 정수 (위의 경우 7)를 출력하는 알고리즘을 설계합니다.

해결책 (지금까지)

나는 이것을 생각 해냈다.

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i++) {
        ret ^= a[i];
    }
    for (int i = 0; i < b.length; i++) {
        ret ^= b[i];
    }
    return ret;
}

수업에서 제공되는 "공식"솔루션 :

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i++) {
        ret += a[i];
    }
    for (int i = 0; i < b.length; i++) {
        ret -= b[i];
    }
    return Math.abs(ret);
}

그래서 둘 다 개념적으로 같은 일을하고 있습니다. 그리고 소정의 a길이 M이고, b다음 두 솔루션은 O (m + n)은 시간을 실행 한 길이이고, n은.

질문

나는 나중에 선생님과 이야기를 나눴고 그는 더 빠른 방법이 있다고 암시 했습니다. 솔직히 나는 방법을 모르겠다. 요소 가 고유 한지 확인하려면 최소한 모든 요소를 ​​살펴 봐야 할 것 같습니다. 적어도 O (m + n) ... 맞죠?

더 빠른 방법이 있습니까? 그렇다면 그것은 무엇입니까?

---

주석에서 HotLick의 제안을 사용하여 Java에서 수행 할 수있는 가장 빠른 방법 일 것입니다. b.length == a.length + 1따라서 b는 여분의 "고유"요소가있는 더 큰 배열 이라고 가정합니다 .

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    int i;
    for (i = 0; i < a.length; i++) {
        ret = ret ^ a[i] ^ b[i];
    }
    return ret ^ b[i];
}

가정을 할 수 없더라도 a 또는 b가 고유 한 요소를 가진 더 큰 배열이 될 수있는 경우를 포함하도록 쉽게 확장 할 수 있습니다. 그래도 여전히 O (m + n)이고 루프 / 할당 오버 헤드 만 줄어 듭니다.

편집하다:

언어 구현의 세부 사항으로 인해 이것은 여전히 ​​(놀랍게도) CPython에서 수행하는 가장 빠른 방법입니다.

def getUniqueElement1(A, B):
    ret = 0
    for a in A: ret = ret ^ a
    for b in B: ret = ret ^ b
    return ret

timeit모듈로 이것을 테스트 했고 흥미로운 결과를 찾았습니다. longhand ret = ret ^ a가 실제로 속기보다 Python에서 더 빠릅니다 ret ^= a. 또한 루프의 요소를 반복하는 것은 인덱스를 반복 한 다음 Python에서 첨자 연산을 수행하는 것보다 훨씬 빠릅니다. 그렇기 때문에이 코드는 Java를 복사하려고했던 이전 방법보다 훨씬 빠릅니다.

이야기의 교훈은 그 질문이 어쨌든 가짜이기 때문에 정답이 없다는 것입니다. OP가 아래의 다른 답변에서 언급했듯이, 당신은 이것에 대해 O (m + n)보다 더 빨리 갈 수 없으며 그의 선생님은 단지 다리를 당기고있었습니다. 따라서 문제는 두 배열의 모든 요소를 ​​반복하고 모든 요소의 XOR을 누적하는 가장 빠른 방법을 찾는 것으로 줄어 듭니다. 이는 전적으로 언어 구현에 의존한다는 것을 의미하며, 전체 알고리즘이 변경되지 않기 때문에 어떤 구현을 사용하든 진정한 "가장 빠른"솔루션을 얻으려면 몇 가지 테스트를 수행해야합니다.

---

이제 더 빠른 솔루션을 기대하는 분들께 사과드립니다. 선생님이 저와 약간 재미있게 지내셨 고 저는 그가 말하는 요점을 완전히 놓쳤습니다.

내가 의미하는 바를 명확히하는 것으로 시작해야합니다.

그는 그것을 하는 더 빠른 방법 이 있다고 암시했다

우리 대화의 요지는 이것이었습니다. 그는 제 XOR 접근 방식이 흥미 롭다고 말했고, 제가 어떻게 제 솔루션에 도달했는지에 대해 잠시 이야기했습니다. 그는 내 솔루션이 최적이라고 생각하는지 물었습니다. 나는 (내 질문에서 언급 한 이유 때문에) 말했다. 그러자 그는 " 확실 합니까?" 라고 물었습니다. 그의 얼굴을 보면 "smug"라고만 설명 할 수 있습니다. 나는 망설 였지만 그렇다고 말했다. 그는 더 나은 방법을 생각할 수 있는지 물었습니다. 나는 "빠른 방법이 있다는 뜻입니까?" 그러나 그는 나에게 솔직한 대답을하는 대신 그것에 대해 생각하라고 말했습니다. 나는 그럴 것이라고 말했다.

그래서 저는 제 선생님이 제가 모르는 것을 알고 있다고 생각했습니다. 그리고 하루 동안 아무것도 생각하지 않고 여기에 왔습니다.

선생님이 실제로 원했던 것은 내 솔루션 이 더 나은 솔루션을 찾으려는 것이 아니라 최적의 솔루션이라고 방어 하는 것이 었습니다 . 그가 말했듯이, 좋은 알고리즘을 만드는 것은 쉬운 부분이고 어려운 부분은 그것이 작동한다는 것을 증명하는 것입니다 (그리고 그것이 최고라는 것). 그는 훨씬 더 적은 시간이 소요될 수있는 O (n)의 간단한 증명을 작성하는 대신 Find-A-Better-Way Land에서 너무 많은 시간을 보냈다는 것이 매우 재밌다고 생각했습니다 (우리는 그렇게했습니다. 관심이 있습니다).

그래서 여기서 큰 교훈을 배웠습니다. 나는 그것이라고 생각하기 때문에 나는 Shashank 굽타의 답변을 수용 할 수 있습니다 않는 질문이 결함에도 불구하고, 원래의 질문에 대답 관리 할 수 있습니다.

증명을 입력하는 동안 찾은 깔끔한 작은 Python 한 줄로 여러분을 남겨 두겠습니다. 더 이상 효율적이지는 않지만 좋아합니다.

def getUniqueElement(a, b):
    return reduce(lambda x, y: x^y, a + b)

매우 비공식적 인 "증거"

하자 질문에서 원래 두 개의 배열로 시작 a하고 b:

int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};

여기서 더 짧은 배열에는 length가 n있고 긴 배열에는 length가 있어야합니다 n + 1. 선형 복잡성을 증명하는 첫 번째 단계는 배열을 세 번째 배열에 함께 추가하는 것입니다 (우리는이를라고 부릅니다 c).

int[] c = {6, 5, 6, 3, 4, 2, 5, 7, 6, 6, 2, 3, 4};

which has length 2n + 1. Why do this? Well, now we have another problem entirely: finding the element that occurs an odd number of times in c (from here on "odd number of times" and "unique" are taken to mean the same thing). This is actually a pretty popular interview question and is apparently where my teacher got the idea for his problem, so now my question has some practical significance. Hooray!

Let's assume there is an algorithm faster than O(n), such as O(log n). What this means is that it will only access some of the elements of c. For example, an O(log n) algorithm might only have to check log(13) ~ 4 of the elements in our example array to determine the unique element. Our question is, is this possible?

First let's see if we can get away with removing any of the elements (by "removing" I mean not having to access it). How about if we remove 2 elements, so that our algorithm only checks a subarray of c with length 2n - 1? This is still linear complexity, but if we can do that then maybe we can improve upon it even further.

So, let's choose two elements of c completely at random to remove. There are actually several things that could happen here, which I'll summarize into cases:

// Case 1: Remove two identical elements
{6, 5, 6, 3, 4, 2, 5, 7, 2, 3, 4};

// Case 2: Remove the unique element and one other element
{6, 6, 3, 4, 2, 5, 6, 6, 2, 3, 4};

// Case 3: Remove two different elements, neither of which are unique
{6, 5, 6, 4, 2, 5, 7, 6, 6, 3, 4};

What does our array now look like? In the first case, 7 is still the unique element. In the second case there is a new unique element, 5. And in the third case there are now 3 unique elements...yeah it's a total mess there.

Now our question becomes: can we determine the unique element of c just by looking at this subarray? In the first case we see that 7 is the unique element of the subarray, but we can't be sure it is also the unique element of c; the two removed elements could have just as well been 7 and 1. A similar argument applies for the second case. In case 3, with 3 unique elements we have no way of telling which two are non-unique in c.

It becomes clear that even with 2n - 1 accesses, there is just not enough information to solve the problem. And so the optimal solution is a linear one.

Of course, a real proof would use induction and not use proof-by-example, but I'll leave that to someone else :)

---

You can store the count of each value in a collection such as an array or hash map. O(n) then you can check the values of the other collection and stop as soon as you know you have a miss match. This could mean you only search half the second array on average.

---

This is a little bit faster:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    int i;
    for (i = 0; i < a.length; i++) {
        ret += (a[i] - b[i]);
    }
    return Math.abs(ret - b[i]);
}

It's O(m), but the order doesn't tell the whole story. The loop part of the "official" solution has about 3 * m + 3 * n operations, and the slightly faster solution has 4 * m.

(Counting the loop "i++" and "i < a.length" as one operation each).

-Al.

---

Assuming only one element was added, and the arrays were identical to start with, you could hit O(log(base 2) n).

The rationale is that any array is subject to searching binary-ly O(log n). Except that in this case you are not searching for a value in an ordered array, you are searching for the first non-matching element. In such a circumstance a[n] == b[n] means that you are too low, and a[n] != b[n] means that you might be too high, unless a[n-1] == b[n-1].

The rest is basic binary search. Check the middle element, decide which division must have the answer, and do a sub-search on that division.

---

Let's say that there are two unsorted integer arrays a and b, with element repetition allowed. They are identical (with respect to contained elements) except one of the arrays has an extra element ..

You may note that I emphasised two point in your original question, and I'm adding an extra assumption of that the values are non-zero.

In C#, you can do this:

int[, , , , ,] a=new int[6, 5, 6, 3, 4, 2];
int[, , , , , ,] b=new int[5, 7, 6, 6, 2, 3, 4];
Console.WriteLine(b.Length/a.Length);

See? Whatever the extra element is, you will always know it by simply dividing their length.

With these statements, we are not storing the given series of integers as values to arrays, but as their dimensions.

As whatever the shorter series of integers is given, the longer one should have only one extra integer. So no matter the order of the integers, without the extra one, the total size of these two multi-dimensional array are identical. The extra dimension times the size of the longer, and to divide by the size of the shorter, we know what is the extra integer.

This solution would works only for this particular case as I quoted from your question. You might want to port it to Java.

This is just a trick, as I thought the question itself is a trick. We definitely will not consider it as a solution for production.

---

Caution, it is wrong to use the O(n + m) notation. There is but one size parameter which is n (in the asymptotic sense, n and n+1 are equal). You should just say O(n). [For m > n+1, the problem is different and more challenging.]

As pointed by others, this is optimal as you must read all values.

All you can do is reducing the asymptotic constant. There is little room for improvement, as the obvious solutions are already very efficient. The single loop in (10) is probably hard to beat. Unrolling it a bit should improve (slightly) by avoiding a branch.

If your goal is sheer performance, than you should turn to non-portable solutions such as vectorization (using the AXV instructions, 8 ints at a time) and parallelization on multicores or GPGPU. In good old dirty C and a 64 bits processor, you could map the data to an array of 64 bit ints and xor the elements two pairs at a time ;)

---

I think this is similar to Matching nuts and bolts problem.

You could achieve this possibly in O(nlogn). Not sure if thats smaller than O(n+m) in this case.

---

There simply is no faster algorithm. The ones presented in the question are in O(n). Any arithmetic "trick" to solve this will require at least each element of both arrays to be read once, so we stay in O(n) (or worse).

Any search strategy that is in a real subset of O(n) (like O(log n)) will require sorted arrays or some other prebuild sorted structure (binary tree, hash). All sorting algorithms known to mankind are at least O(n*log n) (Quicksort, Hashsort) at average which is worse than O(n).

Therefore, from a mathematical point of view, there is no faster algorithm. There might be some code optimizations, but they won't matter on large scale, as runtime will grow linear with the length of the array(s).

참고URL : https://stackoverflow.com/questions/19203868/faster-algorithm-to-find-unique-element-between-two-arrays