셔플 된 연속 정수 배열에서 중복 요소를 찾는 방법은 무엇입니까?
최근 어딘가에서 질문을 보았습니다.
1001 개의 정수 배열이 있다고 가정합니다. 정수는 무작위 순서이지만 각 정수는 1에서 1000 (포함) 사이임을 알고 있습니다. 또한 두 번 발생하는 하나의 숫자를 제외하고 각 숫자는 배열에 한 번만 나타납니다. 배열의 각 요소에 한 번만 액세스 할 수 있다고 가정하십시오. 반복되는 숫자를 찾는 알고리즘을 설명하십시오. 알고리즘에서 보조 기억 장치를 사용한 경우 필요하지 않은 알고리즘을 찾을 수 있습니까?
내가 알고에 관심은있다 두 번째 부분 , 즉, 보조 기억 장치를 사용하지 않고 . 당신은 어떤 생각이 있습니까?
모두 더하고 1001 개의 숫자 만 사용 된 경우 예상되는 합계를 뺍니다.
예 :
Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10
Input - Expected => 2
업데이트 2 : 일부 사람들은 XOR을 사용하여 중복 번호를 찾는 것이 해킹이나 트릭이라고 생각합니다. 내 공식 응답은 "중복 번호를 찾고 있지 않습니다. 비트 세트 배열에서 중복 패턴을 찾고 있습니다. XOR은 비트 세트를 조작하는 데 ADD보다 확실히 더 적합합니다." :-)
업데이트 : 잠자리에 들기 전에 재미로, 여기에 추가 스토리지 (루프 카운터도 아님)가 필요하지 않고 각 어레이 요소를 한 번만 터치하고 비파괴 적이며 전혀 확장되지 않는 "한 줄"대체 솔루션이 있습니다. -)
printf("Answer : %d\n",
array[0] ^
array[1] ^
array[2] ^
// continue typing...
array[999] ^
array[1000] ^
1 ^
2 ^
// continue typing...
999^
1000
);
컴파일러는 실제로 컴파일 시간에 해당 표현식의 후반부를 계산하므로 "알고리즘"은 정확히 1002 개의 작업으로 실행됩니다.
그리고 배열 요소 값도 컴파일 타임에 알고 있으면 컴파일러는 전체 문을 상수로 최적화합니다. :-)
원래 솔루션 : 올바른 답을 찾기 위해 작동하지만 질문의 엄격한 요구 사항을 충족하지 않습니다. 하나의 추가 정수를 사용하여 루프 카운터를 유지하고 각 배열 요소에 세 번 액세스합니다. 두 번은 현재 반복에서 읽고 쓰고 한 번은 다음 반복에서 읽습니다.
배열을 통과 할 때 현재 요소의 인덱스를 저장하려면 적어도 하나의 추가 변수 (또는 CPU 레지스터)가 필요합니다.
하지만 그 외에도 N에 대해 MAX_INT까지 안전하게 확장 할 수있는 파괴 알고리즘이 있습니다.
for (int i = 1; i < 1001; i++)
{
array[i] = array[i] ^ array[i-1] ^ i;
}
printf("Answer : %d\n", array[1000]);
간단한 힌트와 함께 이것이 왜 당신에게 작동하는지 알아내는 연습을 떠날 것입니다 :-) :
a ^ a = 0
0 ^ a = a
Franci Penov의 비파괴 솔루션 버전.
이것은 XOR운영자 를 사용하여 수행 할 수 있습니다 .
우리는 크기의 배열이 있다고 가정하자 5: 4, 3, 1, 2, 2
인덱스에 있습니다 : 0, 1, 2, 3, 4
이제 XOR모든 요소와 모든 인덱스를 수행하십시오. 2중복 요소 인을 얻습니다 . 이것은 0XORing에서 역할을하지 않기 때문에 발생합니다 . 나머지 n-1인덱스 n-1는 배열의 동일한 요소 와 쌍을 이루고 배열에서 쌍을 이루지 않는 유일한 요소 는 중복됩니다.
int i;
int dupe = 0;
for(i = 0; i < N; i++) {
dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.
이 솔루션의 가장 큰 특징은 추가 기반 솔루션에서 볼 수있는 오버플로 문제가 발생하지 않는다는 것입니다.
이것은 인터뷰 질문이므로 추가 기반 솔루션으로 시작하여 오버플로 제한을 식별 한 다음 XOR기반 솔루션 을 제공하는 것이 가장 좋습니다.:)
이것은 추가 변수를 사용하므로 질문의 요구 사항을 완전히 충족하지 못합니다.
모든 숫자를 더하십시오. 최종 합계는 1 + 2 + ... + 1000+ 중복 숫자입니다.
Francis Penov의 솔루션을 의역하기 위해.
(일반적인) 문제는 다음과 같습니다 : 홀수 번 반복되는 하나의 값을 제외하고 짝수 번 반복되는 요소 만 포함하는 임의 길이의 정수 배열이 주어지면이 값을 찾으십시오.
해결책은 다음과 같습니다.
acc = 0
for i in array: acc = acc ^ i
현재 문제는 적응입니다. 트릭은 두 번 반복되는 요소를 찾아야하기 때문에이 단점을 보완하기 위해 솔루션을 조정해야한다는 것입니다.
acc = 0
for i in len(array): acc = acc ^ i ^ array[i]
프랜시스의 솔루션은 결국 전체 배열을 파괴하지만 (그런데 첫 번째 또는 마지막 요소 만 파괴 할 수 있지만 ...)
하지만 인덱스에 대한 추가 저장 공간이 필요하기 때문에 추가 정수도 사용하면 용서받을 수있을 것입니다. 제한은 아마도 배열을 사용하지 못하게하려는 것이기 때문일 것입니다.
O(1)공간 이 필요하다면 더 정확하게 표현되었을 것입니다 (1000은 여기서 임의적이기 때문에 N으로 볼 수 있습니다).
모든 숫자를 추가하십시오. 정수 1..1000의 합은 (1000 * 1001) / 2입니다. 당신이 얻는 것과 다른 것은 당신의 번호입니다.
정확한 숫자가 1-1000임을 알고 있다면 결과를 더하고 합계에서 500500( sum(1, 1000))를 뺄 수 있습니다 . 이것은 반복되는 숫자를 줄 것 sum(array) = sum(1, 1000) + repeated number입니다.
글쎄요, 이렇게하는 아주 간단한 방법이 있습니다 ... 1에서 1000 사이의 숫자는 반복되는 숫자를 제외하고 정확히 한 번 발생합니다 .... 그래서, 1 .... 1000의 합은 500500입니다. 따라서 알고리즘은 다음과 같습니다.
합계 = 0 배열의 각 요소에 대해 : 합계 + = 배열의 해당 요소 number_that_occurred_twice = 합계-500500
Python의 한 줄 솔루션
arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2
작동 이유에 대한 설명은 @Matthieu M.의 답변에 있습니다.
n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s
public static void main(String[] args) {
int start = 1;
int end = 10;
int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
System.out.println(findDuplicate(arr, start, end));
}
static int findDuplicate(int arr[], int start, int end) {
int sumAll = 0;
for(int i = start; i <= end; i++) {
sumAll += i;
}
System.out.println(sumAll);
int sumArrElem = 0;
for(int e : arr) {
sumArrElem += e;
}
System.out.println(sumArrElem);
return sumArrElem - sumAll;
}
추가 저장 공간이 필요하지 않습니다 (루프 변수 제외).
int length = (sizeof array) / (sizeof array[0]);
for(int i = 1; i < length; i++) {
array[0] += array[i];
}
printf(
"Answer : %d\n",
( array[0] - (length * (length + 1)) / 2 )
);
인수와 호출 스택이 보조 기억 장치로 간주됩니까?
int sumRemaining(int* remaining, int count) {
if (!count) {
return 0;
}
return remaining[0] + sumRemaining(remaining + 1, count - 1);
}
printf("duplicate is %d", sumRemaining(array, 1001) - 500500);
편집 : 테일 콜 버전
int sumRemaining(int* remaining, int count, int sumSoFar) {
if (!count) {
return sumSoFar;
}
return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]);
}
printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500);
public int duplicateNumber(int[] A) {
int count = 0;
for(int k = 0; k < A.Length; k++)
count += A[k];
return count - (A.Length * (A.Length - 1) >> 1);
}
삼각형 숫자 T (n)은 1에서 n까지 n 개의 자연수의 합입니다. n (n + 1) / 2로 나타낼 수 있습니다. 따라서 주어진 1001 개의 자연수 중에서 하나의 숫자 만 중복된다는 것을 알면 주어진 모든 숫자를 쉽게 합하고 T (1000)을 뺄 수 있습니다. 결과에는이 중복이 포함됩니다.
삼각수 T (n)의 경우 n이 10의 거듭 제곱이면 10 진수 표현을 기반으로이 T (n)을 찾는 아름다운 방법도 있습니다.
n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s
모든 요소를 더한 다음 모든 인덱스의 합계를 빼는 것을 지원하지만 요소 수가 너무 많으면 작동하지 않습니다. 즉 정수 오버플로가 발생합니다! 그래서 정수 오버플로의 가능성을 크게 줄일 수있는이 알고리즘을 고안했습니다.
for i=0 to n-1
begin:
diff = a[i]-i;
dup = dup + diff;
end
// where dup is the duplicate element..
그러나이 방법으로는 중복 요소가있는 인덱스를 찾을 수 없습니다!
For that I need to traverse the array another time which is not desirable.
Improvement of Fraci's answer based on the property of XORing consecutive values:
int result = xor_sum(N);
for (i = 0; i < N+1; i++)
{
result = result ^ array[i];
}
Where:
// Compute (((1 xor 2) xor 3) .. xor value)
int xor_sum(int value)
{
int modulo = x % 4;
if (modulo == 0)
return value;
else if (modulo == 1)
return 1;
else if (modulo == 2)
return i + 1;
else
return 0;
}
Or in pseudocode/math lang f(n) defined as (optimized):
if n mod 4 = 0 then X = n
if n mod 4 = 1 then X = 1
if n mod 4 = 2 then X = n+1
if n mod 4 = 3 then X = 0
And in canonical form f(n) is:
f(0) = 0
f(n) = f(n-1) xor n
My answer to question 2:
Find the sum and product of numbers from 1 -(to) N, say SUM, PROD.
Find the sum and product of Numbers from 1 - N- x -y, (assume x, y missing), say mySum, myProd,
Thus:
SUM = mySum + x + y;
PROD = myProd* x*y;
Thus:
x*y = PROD/myProd; x+y = SUM - mySum;
We can find x,y if solve this equation.
In the aux version, you first set all the values to -1 and as you iterate check if you have already inserted the value to the aux array. If not (value must be -1 then), insert. If you have a duplicate, here is your solution!
In the one without aux, you retrieve an element from the list and check if the rest of the list contains that value. If it contains, here you've found it.
private static int findDuplicated(int[] array) {
if (array == null || array.length < 2) {
System.out.println("invalid");
return -1;
}
int[] checker = new int[array.length];
Arrays.fill(checker, -1);
for (int i = 0; i < array.length; i++) {
int value = array[i];
int checked = checker[value];
if (checked == -1) {
checker[value] = value;
} else {
return value;
}
}
return -1;
}
private static int findDuplicatedWithoutAux(int[] array) {
if (array == null || array.length < 2) {
System.out.println("invalid");
return -1;
}
for (int i = 0; i < array.length; i++) {
int value = array[i];
for (int j = i + 1; j < array.length; j++) {
int toCompare = array[j];
if (value == toCompare) {
return array[i];
}
}
}
return -1;
}
'code' 카테고리의 다른 글
| 드롭 다운 방법 (0) | 2020.10.26 |
|---|---|
| 뒤로 버튼과 같은 버튼을 사용하여 현재 조각을 닫는 방법은 무엇입니까? (0) | 2020.10.25 |
| CSS 기능 / 기능 감지를 사용하여 IE11 감지 (0) | 2020.10.25 |
| VSCode가 HTML을 자동 완성하지 않음 (0) | 2020.10.25 |
| Django에서 SELECT MAX를 수행하는 방법은 무엇입니까? (0) | 2020.10.25 |