n개의 다른 숫자 배열이 있다고 가정합니다. n은 최대 32,000일 수 있습니다. 배열에 중복 항목이 있을 수 있으며 n 값이 무엇인지 모릅니다. 이제 메모리가 4KB뿐인 경우 배열의 모든 중복 항목을 어떻게 표시할까요?
따라서 입력이 [2, 6, 2, 11, 13, 11]과 같으면 지정된 배열에서 2와 11이 두 번 이상 나타나므로 출력은 [2,11]이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
하나의 바이트 배열 유형 데이터 구조 bit_arr 생성, 다음 메소드가 있습니다.
-
생성자를 정의하려면 n
이 필요합니다. -
arr :=크기(n / 2^5) + 1의 배열, 0으로 채움
-
get_val() 함수를 정의합니다. 이것은 pos를 취할 것입니다
-
인덱스 :=위치 / 2^5
-
bitNo :=위치 AND 31
-
(arr[index] AND (2^bitNo))가 0과 같지 않으면 true를 반환합니다.
-
set_val() 함수를 정의합니다. 이것은 pos를 취할 것입니다
-
인덱스 :=위치 / 2^5
-
bitNo :=위치 AND 31
-
arr[인덱스] :=arr[인덱스] OR (2^bitNo)
-
기본 방법에서 다음을 수행하십시오 -
-
arr :=bit_arr(320000)
-
범위 0에서 arr 크기까지의 i에 대해
-
num :=arr[i]
-
arr.get_val(num)이 0이 아니면
-
표시 번호
-
-
그렇지 않으면
-
arr의 set_val(숫자)
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class bit_arr: def __init__(self, n): self.arr = [0] * ((n >> 5) + 1) def get_val(self, pos): self.index = pos >> 5 self.bitNo = pos & 31 return (self.arr[self.index] & (1 << self.bitNo)) != 0 def set_val(self, pos): self.index = pos >> 5 self.bitNo = pos & 31 self.arr[self.index] |= (1 << self.bitNo) def is_duplicate(arr): arr = bit_arr(320000) for i in range(len(arr)): num = arr[i] if arr.get_val(num): print(num, end = " ") else: arr.set_val(num) arr = [2, 6, 2, 11, 13, 11] is_duplicate(arr)
입력
[2, 6, 2, 11, 13, 11]
출력
2 11