약간의 고대 알고리즘 마법 또는 LeetCode의 흥미로운 일련의 작업 해결

얼마 전 저는 leetcode.com 웹사이트에서 일련의 재미있는 작업을 발견했습니다. 작업 자체는 그다지 어렵지 않지만 솔루션이 매우 흥미로울 수 있습니다. 게다가 이런 유형의 문제는 대기업 면접에서 자주 등장하는데, 그 해결 방법을 이해하면 꽤 도움이 될 수 있다.

첫 번째 작업은 136입니다. 단일 숫자(쉬움)

모든 요소가 하나를 제외하고 두 번 나타나는 비어 있지 않은 정수 배열이 있는 경우 쌍이 없는 요소를 찾아야 합니다. O(n) 시간 복잡도와 지속적인 추가 메모리로 문제를 해결합니다.

예시 1:

입력: 숫자 = [1, 3, 3, 2, 6, 2, 1]

출력: 6

예 2:

입력: 숫자 = [12, 1, 1, 7, 1, 12, 1]

출력: 7

예시 3:

입력: 숫자 = [6]

출력: 6

피연산자가 다른 경우에만 1을 생성하는 XOR 함수 속성을 활용하겠습니다. 배열의 모든 요소를 탐색하고 비트별 XOR을 수행하여 동일한 비트 값을 모두 0으로 만듭니다. 결과적으로 남은 것은 원하는 결과가 될 것입니다.

다음은 짧은 Python3 솔루션 코드입니다.

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

우리는 정수가 차지하는 만큼의 추가 메모리만 사용하고 주어진 배열을 통해 단일 패스로 솔루션을 찾으므로 O(n) 복잡성이 발생합니다. 이것은 간결하고 우아한 솔루션입니다.

두 번째 문제는 137입니다. 단일 숫자 II(중간 난이도)

모든 요소가 하나를 제외하고 세 번 나타나고 한 요소만 한 번 나타나는 비어 있지 않은 정수 배열이 있는 경우 이 고유한 요소를 찾아야 합니다. O(n) 시간 복잡도와 지속적인 추가 메모리로 문제를 해결합니다.

예시 1:

입력: 숫자 = [3, 1, 3, 3]

출력: 1

예 2:

입력: 숫자 = [12, 1, 1, 5, 1, 12, 12]

출력: 5

예시 3:

입력: 숫자 = [6]

출력: 6

불행하게도 이 경우에는 필요한 위치의 쌍을 이루는 비트를 0으로 바꿀 수 없기 때문에 이전 트릭을 사용할 수 없습니다. 주어진 배열을 이전 작업의 형식으로 변환한 다음 비슷한 방식으로 해결하고 싶을 것입니다.

이런 식으로 추론하면 배열을 탐색하는 동안 이미 숫자 N을 두 번(또는 세 번) 만났다는 것을 안다면 우리가 얻는 합계에 N을 사용하여 추가 XOR을 추가할 수 있다는 것을 쉽게 알 수 있습니다. 이렇게 하면 이 숫자에 대한 최종 XOR이 짝수가 되어 최종 합계에서 해당 숫자가 제거되고 남은 것은 우리의 대답이 됩니다.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

불행하게도 이 솔루션은 메모리 측면에서 최대 (len(nums)-1)/3이 필요하며 이는 지속적인 소비로 간주할 수 없으므로 다른 솔루션을 찾아야 합니다.

접근 방식을 바꿔서 시도해 보겠습니다.

이전에는 XOR(덧셈 모듈로 2를 나타냄)을 사용했습니다. 덧셈 모듈로 3을 구현했다면 이전 예제의 트릭을 쉽게 적용할 수 있었을 것입니다.

처음 접할 때 답에 숫자를 입력하고, 두 번째에는 누산기에 넣고, 세 번째에는 답과 누산기를 모두 0으로 만들 수 있다면 한 번의 통과로 문제를 해결하는 데 도움이 될 것입니다. 작업 요구 사항을 충족하는 두 개의 정수와 정확히 동일한 추가 메모리 소비 목록입니다.

이제 좀 더 비트별 마법을 적용해 보겠습니다.

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

이런 식으로 모든 삼중 숫자는 0으로 처리되고 단 한 번만 나타나는 숫자만 남습니다.

세 번째 과제는 260입니다. 단일 숫자 III(중간 난이도)

한 번만 나타나는 두 요소를 제외하고 모든 요소가 두 번 나타나는 비어 있지 않은 정수 배열이 있는 경우 이러한 고유한 요소를 찾아야 합니다. 목표는 O(n) 시간 복잡도와 지속적인 추가 메모리로 문제를 해결하는 것이며 고유 요소의 순서는 중요하지 않습니다.

예시 1:

입력: 숫자 = [1, 2, 1, 3, 2, 5]

출력: [3, 5]

예 2:

입력: 숫자 = [1, -2]

출력: [-2, 1]

분명히 첫 번째 작업을 해결할 때와 마찬가지로 XOR 연산을 사용하여 모든 쌍의 숫자를 쉽게 제거할 수 있습니다. 그러면 작업의 복잡성은 고유 숫자 중 하나를 식별하는 데 있으며, 그 후 두 번째 숫자는 XOR 합계와 XOR 연산을 통해 쉽게 계산할 수 있습니다.

이를 달성하려면 이러한 고유 숫자 사이에서 다른 비트를 찾으면 됩니다. 그런 다음 배열을 다시 반복하여 XOR 합계를 수행하고 결과를 이 비트가 설정된 숫자와 0인 숫자에 대해 두 그룹으로 나눕니다. 결과적으로 원하는 고유 요소를 얻습니다.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

배열을 두 번 반복해야 함에도 불구하고 복잡성은 여전히 O(n)이고 메모리 소비는 정수 2개에 불과합니다.

주의: Python의 int가 다른 언어의 int와 정확히 동일하지는 않지만 크기를 상수로 간주합니다.