얼마 전 저는 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와 정확히 동일하지는 않지만 크기를 상수로 간주합니다.
