Số thống trị thập phân trong một mảng

Question

Gần đây tôi đã xem câu hỏi phỏng vấn này:

Bạn được cung cấp n số thực trong một mảng. Một số trong mảng được gọi là tỷ lệ thập phân nếu nó xuất hiện nhiều hơn n/10 lần trong mảng. Đưa ra một thuật toán thời gian O (n) để xác định xem mảng đã có có ưu thế thập phân hay không.

Bây giờ tôi có thể nghĩ đến một vài cách để giải quyết việc này, và bất kỳ sự tổng quát của câu hỏi này (tức là tìm thấy bất kỳ số xuất hiện K lần trong một mảng)

Người ta có thể được để thực hiện một bảng băm trong đường chuyền 1 , và sau đó đếm số lần xuất hiện trong đường chuyền 2, đó sẽ là O (n), nhưng sử dụng O (n) không gian là tốt,

có một cách using 9 buckets

nhưng, có cách nào chúng tôi có thể làm điều đó trong một không gian liên tục ?? Bất kỳ đề xuất??

[EDIT] tôi đã không kiểm tra các giải pháp 9 xô, độc giả có thể muốn đi qua bình luận nm của dưới

Answer 1

1. làm một vòng lặp và lưu trữ/thêm giá trị trong mảng các số thực int [].

2. thực hiện một vòng lặp khác chia giá trị danh sách mảng thành 10 nếu lớn hơn 1 giá trị thập phân.

Answer 2

Tôi đã vạch ra một cách dựa trên thuật toán bỏ phiếu đa số Boyer-Moore here.

Bạn nhớ (tối đa) (m-1) các yếu tố gần đây đã được nhìn thấy thường xuyên hơn so với các yếu tố khác và số lượng được liên kết. Khi một yếu tố nhớ được nhìn thấy, số lượng của nó được tăng lên. Khi một yếu tố không nhớ được nhìn thấy, nếu có một khe miễn phí, bạn nhớ nó và đặt số của nó là 1, nếu không bạn trừ 1 từ tất cả các đếm của các yếu tố nhớ. Một yếu tố được nhớ có số đếm tới 0 bị lãng quên. Bất kỳ phần tử nào xảy ra với tỷ lệ cao hơn 1/m là một trong những yếu tố được ghi nhớ. Nếu bạn không biết một ưu tiên rằng có m-1 yếu tố xảy ra hơn n/m lần, bạn cần một lần vượt qua thứ hai để đếm số lần xuất hiện của các yếu tố được ghi nhớ.

Chỉnh sửa: Sau khi truy cập vào trang được chỉ định, tôi thấy đó là giải pháp giống hệt, ngoại trừ nó không tính đến những người không chiếm ưu thế.

Khi điều này đã được hoàn thành, bất kỳ biến số nào có số lượng lớn hơn 1 có hơn 10 trường hợp trong danh sách.

không đúng, nhưng tất cả các phần tử thập phân sẽ được ghi nhớ với số lượng >= 1 ở cuối. Tôi chưa đi qua mã ở đó, vì vậy nó có thể chứa lỗi, nhưng thuật toán là chính xác, ngoại trừ thẻ kiểm tra bị thiếu.

Các phản ví dụ đề xuất được xử lý một cách chính xác nếu chúng ta có vượt qua thứ hai, nhà nước tiến hóa

0 1 2 3 4 5 6 7 8 
1 1 1 1 1 1 1 1 1 // coming 9 
0 0 0 0 0 0 0 0 0 // all forgotten, no slots occupied, coming 10 
10 - - - - - - - - 
1 - - - - - - - - // coming 0 
10 0 - - - - - - - 
1 1 - - - - - - - 

ở cuối, có hai khe cắm bị chiếm đóng, 10 và 0 đều nhớ đến với một số trong tổng số 1.10 không phải là số thập phân thống kê, nhưng 0 là và chỉ là số duy nhất, vì sẽ được xác minh bằng lần kiểm tra thứ hai.

Answer 3

public static int[] KthDominants(int[] arr, int kth) 
    { 
     var data = new Dominants(arr.Length, kth); 
     for (int i = 0; i < arr.Length; i++) 
     { 
      data.Push(arr[i]); 
     } 
     return data.ToArray(); 
    } 

Lớp Dominant lưu trữ các bộ đếm kth-1 trong từ điển. Nó sử dụng System.Linq để làm việc với các bộ sưu tập.

public class Dominants 
{ 
    int _size; 
    int _kth; 
    int _grade; 
    Dictionary<int, int> _counters; 

    public Dominants(int size, int kth) 
    { 
     _size = size; 
     _kth = kth; 
     _counters = new Dictionary<int, int>(); 
    } 

    public void Push(int key) 
    { 
     if (_counters.ContainsKey(key)) 
      _counters[key]++; 
     else 
     { 
      // The trick is that the dominant element remains same 
      // if you delete any k distinct items from the array. 
      if (_counters.Count < _kth) 
       _counters.Add(key, 1); 
      else 
      { 
       foreach (var i in _counters.Keys.ToArray()) 
       { 
        if (_counters[i] > 1) 
         _counters[i]--; 
        else 
         _counters.Remove(i); 
       } 
       _grade++; 
      } 
     } 
    } 

    public int[] ToArray() 
    { 
     var cnt = _size/_kth - (_grade + 1); 
     return _counters 
      .Where(i => i.Value > cnt) 
      .Select(i => i.Key) 
      .ToArray(); 
    } 
} 

github

Answer 4

bạn có thể sử dụng 3-way-partitionnhanh chọn để tìm ra (n/10) phần tử lớn nhất thứ của mảng, và sau đó kiểm tra xem đó là số thập phân-ưu thế ; nếu không, hãy lặp lại trong mảng phụ bên phải.

điều này có thể được thực hiện tại chỗ và trong thời gian mong đợi tuyến tính, vì vậy không phải không gian liên tục nghiêm ngặt.