cách AND và một số lượng lớn các mảng số?

Question

Tôi có 200 mảng số nguyên dương được sắp xếp (một số trong số chúng có hơn một triệu số). Tôi cần phải tìm số đầu tiên tồn tại trong mọi mảng. Bạn đề nghị điều gì?

Answer 1

• Giữ chỉ mục trên mọi mảng.
• Bắt đầu với số đầu tiên của mảng đầu tiên làm tham chiếu.
• Là số đầu tiên của mảng thứ n thấp hơn tham chiếu, tăng chỉ mục của nó.
• Là số đầu tiên của mảng thứ n bằng tham chiếu, tăng n và tiếp tục - mảng tiếp theo.
• Là số đầu tiên của mảng thứ n cao hơn tham chiếu, sử dụng số đó làm tham chiếu và bắt đầu lại.
• Nếu n == 201, tham chiếu của bạn tồn tại trong mọi mảng.

Edit: một ví dụ mã:

while n < len(data): 
    item = data[n][indices[n]] 
    if item < reference: 
     indices[n] += 1 
    elif item == reference: 
     n += 1 
    elif item > reference: 
     reference = item 
     n = 0 

print reference 

Answer 2

Bạn có thể thực hiện hợp nhất k trên các mảng và kiểm tra phần tử đầu tiên xuất hiện k lần.

Cách khác là tạo histogram và chọn phần tử đầu tiên xuất hiện k thời gian trong biểu đồ. Một biểu đồ trong java có thể được thực hiện dễ dàng bằng một Map<Element,Integer>

Cả hai giải pháp là O(kn) nơi k là số mảng và n là kích thước trung bình của một mảng, vì vậy nó được về cơ bản tuyến tính trong kích thước của đầu vào.