Ước tính tần số của một phần tử trong một mảng trong thời gian O (n)

Question

Tôi cho rằng tiêu đề có thể gây hiểu lầm một chút, nhưng tôi không thể nghĩ ra một cái nào tốt hơn. Tôi có một mảng A [], tất cả trừ một phần tử có số lần xuất hiện là bội số của 15, ví dụ: 2 xảy ra 30 lần, 3 xảy ra 45 lần. Nhưng một phần tử xảy ra x lần mà x không phải là bội số của 15. Làm thế nào để in số x. Tôi đang tìm một giải pháp tuyến tính mà không có bảng băm.

Cảm ơn.

Answer 1

Có câu hỏi tương tự ở đây, trên StackOverflow, nhưng tôi không thể tìm thấy nó.

Cho phép sử dụng 3 thay vì 15, bởi vì nó sẽ dễ dàng hơn và tôi nghĩ rằng nó hoàn toàn tương đương. Trình tự sẽ là 4, 5, 4, 5, 3, 3, 4, 5, ở dạng nhị phân 100, 101, 100, 101, 11, 11, 100, 101.

Bạn có thể làm như sau: tổng tất cả các giá trị trong ít nhất chút ý nghĩa các con số và đưa phần còn lại hơn 3 (15 ban):

bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0

nếu nó là != 0 sau đó rằng bit là bằng 1 trong số mà chúng tôi đang cố gắng tìm. Bây giờ cho phép di chuyển đến tiếp theo:

bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0

bit3 = (1 + 1 + 1 + 1 + 0 + 0 + 1 + 1) % 3 = 6 % 3 = 0 == 0

Vì vậy, chúng tôi có bit3 == 0, bit2 != 0, bit1 != 0, làm 011. Chuyển đổi sang số thập phân: 3.

Sự phức tạp không gian là O(1) và thời gian phức tạp là O(n * BIT_LENGTH_OF_VARS), nơi BIT_LENGTH_OF_VARS == 8 cho byte, BIT_LENGTH_OF_VARS == 32 cho int, vv Vì vậy, nó có thể lớn, nhưng hằng không ảnh hưởng đến hành vi tiệm cận và O(n * BIT_LENGTH_OF_VARS) thực sự là O(n).

Vậy đó!