Tìm Element Xảy ra lần b trong một loạt các kích thước n * k + b

Question

Mô tả

Cho một mảng kích thước (n*k+b) nơi n phần tử xảy ra lần k và một yếu tố xảy ra lần b, nói cách khác có là n+1 Các phần tử riêng biệt. Cho rằng 0 < b < k tìm phần tử xảy ra b lần.

giải pháp Toan My

1. giải pháp hiển nhiên sẽ được sử dụng băm nhưng nó sẽ không hoạt động nếu những con số rất lớn. Phức tạp là O(n)

2. Sử dụng bản đồ để lưu trữ các tần số của mỗi yếu tố và sau đó đi qua bản đồ để tìm các yếu tố xảy ra b times.As Bản đồ của được thực hiện như cây chiều cao cân phức tạp sẽ O(nlogn).

Cả hai giải pháp của tôi đều được chấp nhận nhưng người phỏng vấn muốn một giải pháp tuyến tính mà không sử dụng băm và gợi ý ông đưa ra là chiều cao cây cố định trong đó bạn đang lưu trữ tần số, nhưng tôi không thể ra giải pháp đúng.

Tôi muốn biết làm thế nào để giải quyết vấn đề này trong thời gian tuyến tính mà không băm?

EDIT:

mẫu:

Input: n=2 b=2 k=3

Aarray: 2 2 2 3 3 3 1 1

Output: 1

Answer 1

Một ý tưởng sử dụng các nhóm theo chu kỳ

Để đoán câu trả lời thứ i, hãy làm theo quy trình sau:

1. Đếm bao nhiêu số trong mảng có thứ i chút bộ, lưu trữ như cnt
2. Nếu cnt % k là khác không, sau đó chút thứ i của câu trả lời được thiết lập. Nếu không thì rõ ràng.

Để đoán số nguyên, lặp lại ở trên cho mỗi bit.

Giải pháp này về mặt kỹ thuật O((n*k+b)*log max N), trong đó max N là giá trị tối đa trong bảng, nhưng vì số bit thường không đổi, giải pháp này tuyến tính ở kích thước mảng.

Không băm, sử dụng bộ nhớ là O(log k * log max N).

thực hiện Ví dụ:

from random import randint, shuffle 

def generate_test_data(n, k, b): 
    k_rep = [randint(0, 1000) for i in xrange(n)] 
    b_rep = [randint(0, 1000)] 
    numbers = k_rep*k + b_rep*b 
    shuffle(numbers) 
    print "k_rep: ", k_rep 
    print "b_rep: ", b_rep 
    return numbers 

def solve(data, k): 
    cnts = [0]*10 
    for number in data: 
     bits = [number >> b & 1 for b in xrange(10)] 
     cnts = [cnts[i] + bits[i] for i in xrange(10)] 
    return reduce(lambda a,b:2*a+(b%k>0), reversed(cnts), 0) 

print "Answer: ", solve(generate_test_data(10, 15, 13), 3) 

Answer 2

Để có một chiều cao liên tục B-cây chứa n các yếu tố riêng biệt, với chiều cao h không đổi, bạn cần z=n^(1/h) trẻ em trên mỗi nút: h=log_z(n), do đó h=log(n)/log(z), do đó log(z)=log(n)/h, do đó z=e^(log(n)/h), do đó z=n^(1/h).

Ví dụ, với n=1000000, h=10, z=3.98, nghĩa là z=4.

Thời gian để đến một nút trong trường hợp đó là O(h.log(z)). Giả sử h và z là "không đổi" (kể từ N=n.k, sau đó log(z)=log(n^(1/h))=log(N/k^(1/h))=ct bằng cách chọn đúng h dựa trên k, sau đó bạn có thể nói rằng O(h.log(z))=O(1) ... Điều này hơi khó tìm, nhưng có thể đó là loại người phỏng vấn ? muốn nghe

Answer 3

tôi giả:

1. các yếu tố của mảng có thể so sánh
2. Chúng tôi biết các giá trị của n và k trước
3. Một giải pháp O (n * k + b..) là goo d đủ.

Hãy để số chỉ xảy ra b lần là S. Chúng tôi đang cố gắng tìm S trong một mảng có kích thước n * k + b.

Bước đệ quy: Tìm phần tử trung bình của mảng mảng hiện tại như trong Sắp xếp nhanh trong thời gian dòng. Gọi phần tử trung bình là M.

Sau bước đệ quy, bạn có một mảng trong đó tất cả các phần tử nhỏ hơn M xảy ra bên trái xuất hiện đầu tiên của M. Tất cả các phần tử M nằm cạnh nhau và tất cả phần tử lớn hơn M ở bên phải của tất cả các lần xuất hiện của M.

Nhìn vào chỉ số của m ngoài cùng bên trái và tính xem S < M hoặc S > = M. Recurse hoặc trên slice trái hoặc slice bên phải.

Vì vậy, bạn đang sắp xếp nhanh nhưng chỉ xóa một phần của các bộ phận bất kỳ lúc nào. Bạn sẽ recurse O (logN) lần nhưng mỗi lần với 1/2, 1/4, 1/8, .. kích cỡ của mảng ban đầu, vì vậy tổng thời gian sẽ vẫn là O (n).

Làm rõ: Giả sử n = 20 và k = 10. Sau đó, có 21 phần tử riêng biệt trong mảng, 20 trong số đó xuất hiện 10 lần và lần xuất hiện cuối cùng, giả sử 7 lần. Tôi tìm thấy phần tử trung bình, giả sử nó là 1111. Nếu S < 1111 hơn chỉ số xuất hiện ngoài cùng bên trái của 1111 sẽ nhỏ hơn 11 * 10. Nếu S> = 1111 thì chỉ số sẽ bằng 11 * 10.

Ví dụ đầy đủ: n = 4. k = 3. Mảng = {1,2,3,4,5,1,2,3,4,5,1,2,3,5} Sau bước đệ quy đầu tiên tôi tìm thấy phần tử trung bình là 3 và mảng giống như sau: {1,2,1,2,1,2,3,3,3,5,4,5,5,4} Có 6 các phần tử bên trái của 3. 6 là bội số của k = 3. Vì vậy, mỗi phần tử phải xuất hiện 3 lần ở đó. Vì vậy S> = 3. Recurse ở phía bên phải. Và cứ thế.

Answer 4

CẬP NHẬT: một sử dụng băm này, vì vậy nó không phải là một câu trả lời tốt :(

trong python này sẽ là thời gian tuyến tính (set sẽ loại bỏ các bản sao):

result = (sum(set(arr))*k - sum(arr))/(k - b) 

Answer 5

Nếu 'k' là chẵn và 'b' là số lẻ, sau đó XOR sẽ làm. :)