Tìm nguyên tố phổ biến độc đáo từ 3 mảng

Question

Vấn đề gốc:
Tôi có 3 hộp mỗi chứa 200 đồng tiền, cho rằng chỉ có một người đã thực hiện cuộc gọi từ tất cả các ba hộp và do đó có một đồng xu trong mỗi hộp có cùng dấu vân tay và phần còn lại của tất cả các đồng tiền có dấu vân tay khác nhau. Bạn phải tìm đồng xu có chứa dấu vân tay giống nhau từ tất cả 3 ô. Vì vậy, chúng tôi có thể tìm thấy dấu vân tay của người đã thực hiện cuộc gọi từ tất cả 3 ô.

Sự cố được chuyển đổi:
Bạn có 3 mảng chứa 200 số nguyên. Cho rằng có một và chỉ một phần tử phổ biến trong 3 mảng này. Tìm phần tử chung.
Vui lòng xem xét giải quyết vấn đề này ngoài không gian O (1) tầm thường và thời gian O (n^3).

Answer 1

Một số cải tiến trong Pelkonen của câu trả lời:
Từ vấn đề chuyển đổi trong OP:

"Cho rằng có một và chỉ một yếu tố chung trong 3 mảng."

Chúng tôi chỉ cần sắp xếp 2 mảng và tìm phần tử chung.

Answer 2

Nếu bạn sắp xếp tất cả các mảng đầu tiên O (n log n) thì sẽ khá dễ dàng để tìm phần tử phổ biến trong thời gian nhỏ hơn O (n^3). Ví dụ, bạn có thể sử dụng tìm kiếm nhị phân sau khi sắp xếp chúng.

Answer 3

Sử dụng bảng băm cho mỗi số nguyên và mã hóa các mục nhập sao cho bạn biết mảng nào đến từ đó - sau đó kiểm tra vị trí có mục nhập từ tất cả 3 mảng. O (n)

Answer 4

Giải pháp O (N): sử dụng bảng băm. H [i] = danh sách của tất cả các số nguyên trong ba mảng ánh xạ tới i.

Đối với tất cả H [i]> 1 kiểm tra xem ba giá trị của nó có giống nhau hay không. Nếu có, bạn có giải pháp của bạn. Bạn có thể làm điều này kiểm tra với các giải pháp ngây thơ ngay cả, nó vẫn nên rất nhanh, hoặc bạn có thể sắp xếp những H [i] và sau đó nó trở nên tầm thường.

Nếu số của bạn tương đối nhỏ, bạn có thể sử dụng H [i] = k nếu tôi xuất hiện k lần trong ba mảng, thì giải pháp là i mà H [i] = 3. Nếu số của bạn là rất lớn , sử dụng một bảng băm mặc dù.

Bạn có thể mở rộng tính năng này để hoạt động ngay cả khi bạn có thể có các thành phần chỉ có thể là hai mảng và cũng có thể có các phần tử lặp lại các phần tử trong một trong các mảng. Nó chỉ trở nên phức tạp hơn một chút, nhưng bạn có thể tự mình tìm ra nó.

Answer 5

Sử dụng đối tượng ánh xạ có thể bắt buộc để tính số lượng tần suất. Lặp lại qua tất cả ba danh sách, tăng số lần xuất hiện trong Hashtable, cho đến khi bạn gặp phải một số với số lần xuất hiện là 3. Đây là O (n), vì không cần sắp xếp.Ví dụ bằng Python:

def find_duplicates(*lists): 
    num_lists = len(lists) 
    counts = {} 
    for l in lists: 
    for i in l: 
     counts[i] = counts.get(i, 0) + 1 
     if counts[i] == num_lists: 
     return i 

Hoặc tương đương, sử dụng bộ:

def find_duplicates(*lists): 
    intersection = set(lists[0]) 
    for l in lists[1:]: 
    intersection = intersection.intersect(set(l)) 
    return intersection.pop() 

Answer 6

Nếu bạn muốn * câu trả lời nhanh nhất:

• Sắp xếp một mảng - thời gian được N log N.
• Đối với mỗi phần tử trong mảng thứ hai, hãy tìm kiếm phần tử đầu tiên. Nếu bạn tìm thấy nó, thêm 1 vào một mảng đồng hành; nếu không thêm 0 - thời gian là N log N, sử dụng N không gian.
• Đối với mỗi số không khác, sao chép mục nhập tương ứng vào mảng tạm thời, nén nó sao cho nó vẫn được sắp xếp - thời gian là N.
• Đối với mỗi phần tử trong mảng thứ ba, tìm kiếm mảng tạm thời; khi bạn tìm thấy một hit, dừng lại. Thời gian là ít hơn N log N.

Dưới đây là mã trong Scala ví dụ minh họa:

import java.util.Arrays 

val a = Array(1,5,2,3,14,1,7) 
val b = Array(3,9,14,4,2,2,4) 
val c = Array(1,9,11,6,8,3,1) 

Arrays.sort(a) 
val count = new Array[Int](a.length) 
for (i <- 0 until b.length) { 
    val j =Arrays.binarySearch(a,b(i)) 
    if (j >= 0) count(j) += 1 
} 
var n = 0 
for (i <- 0 until count.length) if (count(i)>0) { count(n) = a(i); n+= 1 } 
for (i <- 0 until c.length) { 
    if (Arrays.binarySearch(count,0,n,c(i))>=0) println(c(i)) 
} 

Với một chút phức tạp hơn, bạn có thể sử dụng không gian thêm với chi phí được thậm chí phá hoại hơn mảng ban đầu của bạn, hoặc bạn có thể tránh chạm vào mảng ban đầu của bạn ở tất cả tại các chi phí của một không gian N.

---

Chỉnh sửa: * như các nhận xét đã chỉ ra, bảng băm nhanh hơn cho đầu vào không đảo ngược. Đây là "trường hợp xấu nhất nhanh nhất". Trường hợp xấu nhất có thể không được như vậy không trừ khi bạn sử dụng một thuật toán băm thực sự tốt, mà cũng có thể ăn lên nhiều thời gian hơn so với sắp xếp của bạn. Ví dụ: nếu bạn nhân tất cả các giá trị của mình với 2^16, hàm băm nhỏ (ví dụ: chỉ sử dụng số nguyên bitmasked làm chỉ mục) sẽ va chạm mọi lúc trên danh sách ngắn hơn 64k ....

Answer 7

Hãy N = 200, k = 3,

1. Tạo bảng băm H có dung lượng ≥ Nk.

2. Đối với mỗi nguyên tố X trong mảng 1, thiết H [X] để 1.

3. Đối với mỗi phần tử Y trong mảng 2, nếu Y là trong H và H [Y] == 1, thiết H [Y] = 2.

4. Đối với mỗi Z phần tử trong mảng 3, nếu Z là trong H và H [Z] == 2, lợi nhuận Z.

5. throw new InvalidDataGivenByInterviewerException();

Thời gian O (Nk), độ phức tạp không gian O (Nk).