Mảng có kích thước n, với một phần tử n/2 lần

Question

Cho một mảng n số nguyên, trong đó một phần tử xuất hiện nhiều hơn n/2 lần. Chúng ta cần tìm phần tử đó trong thời gian tuyến tính và không gian thêm liên tục.

YAAQ: Còn một câu hỏi khác về mảng.

Answer 1

Tôi có một nghi ngờ tinh quái nó là cái gì dọc theo dòng (trong C#)

// We don't need an array 
public int FindMostFrequentElement(IEnumerable<int> sequence) 
{ 
    // Initial value is irrelevant if sequence is non-empty, 
    // but keeps compiler happy. 
    int best = 0; 
    int count = 0; 

    foreach (int element in sequence) 
    { 
     if (count == 0) 
     { 
      best = element; 
      count = 1; 
     } 
     else 
     { 
      // Vote current choice up or down 
      count += (best == element) ? 1 : -1; 
     } 
    } 
    return best; 
} 

Nghe có vẻ khó xảy ra để làm việc, nhưng nó. (Proof as a postscript file, lịch sự của Boyer/Moore.)

Answer 2

Suy nghĩ đầu tiên của tôi (không đủ) sẽ được:

• Sắp xếp mảng ở vị trí
• Return các yếu tố giữa

Nhưng đó sẽ là O (n log n), như bất kỳ giải pháp đệ quy nào.

Nếu bạn có thể sửa đổi triệt để mảng (và nhiều điều kiện khác được áp dụng), bạn có thể thực hiện việc thay thế các phần tử bằng số lượng của chúng hoặc thứ gì đó. Bạn có biết gì khác về mảng và bạn có được phép sửa đổi nó không?

Chỉnh sửa Để lại câu trả lời của tôi ở đây vì hậu thế, nhưng tôi nghĩ Skeet đã có nó.

Answer 3

Làm thế nào về: chọn ngẫu nhiên một nhóm nhỏ các phần tử K và tìm kiếm các bản sao (ví dụ: 4, 8 đầu tiên, v.v.). Nếu K == 4 thì xác suất không nhận được ít nhất 2 trong số các bản sao là 1/8. nếu K == 8 thì nó sẽ xuống dưới 1%. Nếu bạn không tìm thấy bản sao lặp lại quá trình cho đến khi bạn thực hiện. (giả sử rằng các phần tử khác được phân phối ngẫu nhiên hơn, điều này sẽ thực hiện rất kém với, ví dụ, 49% mảng = "A", 51% của mảng = "B").

ví dụ .:

findDuplicateCandidate: 
    select a fixed size subset. 
    return the most common element in that subset 
    if there is no element with more than 1 occurrence repeat. 
    if there is more than 1 element with more than 1 occurrence call findDuplicate and choose the element the 2 calls have in common  

Đây là một hoạt động nhằm liên tục (nếu tập dữ liệu không phải là xấu) như vậy thì làm một quét tuyến tính của mảng theo thứ tự (N) để xác minh.

Answer 4

Bạn cũng có thể thực hiện sắp xếp phối âm tại chỗ như được mô tả here[pdf] điều này không mất thêm khoảng trống và thời gian tuyến tính. sau đó bạn có thể thực hiện một lần vượt qua đếm các phần tử liên tiếp và kết thúc tại số> n/2.

Answer 5

int findLeader(int n, int* x){ 
    int leader = x[0], c = 1, i; 
    for(i=1; i<n; i++){ 
     if(c == 0){ 
      leader = x[i]; 
      c = 1; 
     } else { 
      if(x[i] == leader) c++; 
      else c--; 
     } 
    } 

    if(c == 0) return NULL; 
    else { 
     c = 0; 
     for(i=0; i<n; i++){ 
      if(x[i] == leader) c++; 
     } 
     if(c > n/2) return leader; 
     else return NULL; 
    } 
} 

Tôi không phải là tác giả của mã này, nhưng điều này sẽ hữu ích cho sự cố của bạn. Phần đầu tiên tìm kiếm một nhà lãnh đạo tiềm năng, lần kiểm tra thứ hai nếu nó xuất hiện nhiều hơn n/2 lần trong mảng.

Answer 6

Tìm trung vị, phải mất O (n) trên một mảng chưa phân loại. Vì nhiều hơn n/2 phần tử bằng với cùng một giá trị, giá trị trung bình bằng với giá trị đó.

Answer 7

Đây là những gì tôi nghĩ ban đầu.

Tôi đã cố gắng giữ nguyên "một phần tử bất biến xuất hiện nhiều hơn n/2 lần", đồng thời giảm tập hợp sự cố.

Cho phép bắt đầu so sánh [i], [i + 1]. Nếu chúng bằng nhau, chúng tôi so sánh [i + i], [i + 2]. Nếu không, chúng tôi sẽ xóa cả [i], [i + 1] khỏi mảng.Chúng tôi lặp lại điều này cho đến khi i> = (kích thước hiện tại)/2. Tại thời điểm này, chúng ta sẽ có phần tử 'THE' chiếm vị trí đầu tiên (kích thước hiện tại)/2. Điều này sẽ duy trì sự bất biến.

Thông báo trước duy nhất là chúng ta giả định rằng mảng nằm trong một danh sách liên kết [cho nó để cung cấp cho một O (n) phức tạp.]

folks nói gì?

-bhupi

Answer 8

trong php --- pls kiểm tra nếu nó đúng

function arrLeader($A){ 
$len = count($A); 
$B = array(); 
$val=-1; 
$counts = array_count_values(array); //return array with elements as keys and occurrences of each element as values 
for($i=0;$i<$len;$i++){ 
    $val = $A[$i]; 
    if(in_array($val,$B,true)){//to avoid looping again and again 
    }else{ 
    if($counts[$val]>$len/2){ 
     return $val; 
    } 
    array_push($B, $val);//to avoid looping again and again 
    } 
} 
return -1; 
} 

Answer 9

int n = A.Length; 
      int[] L = new int[n + 1]; 
      L[0] = -1; 
      for (int i = 0; i < n; i++) 
      { 
       L[i + 1] = A[i]; 
      } 
      int count = 0; 
      int pos = (n + 1)/2; 
      int candidate = L[pos]; 
      for (int i = 1; i <= n; i++) 
      { 
       if (L[i] == candidate && L[pos++] == candidate) 
        return candidate; 
      } 
      if (count > pos) 
       return candidate; 
      return (-1);