Tìm nếu có một yếu tố tự lặp lại n/k lần

Question

Bạn có một kích thước mảng n và liên tụck (bất kỳ)

Bạn có thể đảm nhận mảng là kiểu int (mặc dù nó có thể là của bất kỳ loại nào)

Mô tả thuật toán tìm thấy nếu có (các) yếu tố lặp lại chính nó ít nhất n/k lần ... nếu có trả lại. Làm như vậy trong thời gian tuyến tính (O(n))

Việc nắm bắt: làm thuật toán này (hoặc thậm chí pseudo-code) sử dụng bộ nhớ liên tục và chạy trên mảng chỉ hai lần

Answer 1

1. Tạo một mảng tạm thời có kích thước (k-1) để lưu trữ các phần tử và số lượng của chúng (Phần tử đầu ra sẽ nằm trong số các phần tử k-1 này).

2. Di chuyển qua mảng đầu vào và cập nhật temp [] (thêm/xóa phần tử hoặc tăng/giảm số lượng) cho mọi phần tử đi ngang. Temp [] lưu trữ các ứng cử viên tiềm năng (k-1) ở mọi bước. Bước này có thời gian O (nk).

3. Lặp lại qua các ứng viên tiềm năng cuối cùng (k-1) (được lưu trữ trong temp []). hoặc mọi phần tử, kiểm tra xem nó có thực sự đếm nhiều hơn n/k không. Bước này có thời gian O (nk).

Bước chính là bước 2, cách duy trì (k-1) ứng cử viên tiềm năng tại mọi thời điểm? Các bước được sử dụng trong bước 2 giống như trò chơi nổi tiếng: Tetris. Chúng tôi đối xử với mỗi con số như một mảnh trong Tetris, nằm trong temp tạm thời của chúng tôi []. Nhiệm vụ của chúng tôi là cố gắng giữ cùng một số xếp chồng lên nhau trên cùng một cột (số đếm trong mảng tạm thời được tăng lên).

Consider k = 4, n = 9 
Given array: 3 1 2 2 2 1 4 3 3 

i = 0 
     3 _ _ 
temp[] has one element, 3 with count 1 

i = 1 
     3 1 _ 
temp[] has two elements, 3 and 1 with 
counts 1 and 1 respectively 

i = 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 1 respectively. 

i = 3 
     - - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 2 respectively. 

i = 4 
     - - 2 
     - - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 3 respectively. 

i = 5 
     - - 2 
     - 1 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 2 and 3 respectively. 
Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element. 

i = 6 
     - - 2 
     - 1 2 
temp[] has two elements, 1 and 2 with 
counts as 1 and 2 respectively. 

i = 7 
      - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 2 respectively. 

i = 8   
     3 - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 2, 1 and 2 respectively. 

Cuối cùng, chúng tôi có tối đa số k-1 trong temp []. Các yếu tố trong tạm thời là {3, 1, 2}. Lưu ý rằng số đếm trong temp [] là vô dụng ngay bây giờ, số đếm chỉ cần ở bước 2. Bây giờ chúng ta cần kiểm tra xem số lượng thực tế của các phần tử trong temp [] có lớn hơn n/k (9/4) hay không. Các yếu tố 3 và 2 đã đếm hơn 9/4. Vì vậy, chúng tôi in 3 và 2.

Lưu ý rằng thuật toán không bỏ sót bất kỳ phần tử đầu ra nào. Có thể có hai khả năng, nhiều lần xuất hiện cùng nhau hoặc trải rộng trên mảng. Nếu các lần xuất hiện cùng nhau, thì số lượng sẽ là cao và sẽ không trở thành 0. Nếu xảy ra sự cố, thì phần tử sẽ trở lại trạng thái tạm thời []. Sau đây là C++ thực hiện các thuật toán trên.

// A C++ program to print elements with count more than n/k 
#include<iostream> 
using namespace std; 

// A structure to store an element and its current count 
struct eleCount 
{ 
    int e; // Element 
    int c; // Count 
}; 

// Prints elements with more than n/k occurrences in arr[] of 
// size n. If there are no such elements, then it prints nothing. 
void moreThanNdK(int arr[], int n, int k) 
{ 
    // k must be greater than 1 to get some output 
    if (k < 2) 
     return; 

    /* Step 1: Create a temporary array (contains element 
     and count) of size k-1. Initialize count of all 
     elements as 0 */ 
    struct eleCount temp[k-1]; 
    for (int i=0; i<k-1; i++) 
     temp[i].c = 0; 

    /* Step 2: Process all elements of input array */ 
    for (int i = 0; i < n; i++) 
    { 
     int j; 

     /* If arr[i] is already present in 
      the element count array, then increment its count */ 
     for (j=0; j<k-1; j++) 
     { 
      if (temp[j].e == arr[i]) 
      { 
       temp[j].c += 1; 
       break; 
      } 
     } 

     /* If arr[i] is not present in temp[] */ 
     if (j == k-1) 
     { 
      int l; 

      /* If there is position available in temp[], then place 
       arr[i] in the first available position and set count as 1*/ 
      for (l=0; l<k-1; l++) 
      { 
       if (temp[l].c == 0) 
       { 
        temp[l].e = arr[i]; 
        temp[l].c = 1; 
        break; 
       } 
      } 

      /* If all the position in the temp[] are filled, then 
       decrease count of every element by 1 */ 
      if (l == k-1) 
       for (l=0; l<k; l++) 
        temp[l].c -= 1; 
     } 
    } 

    /*Step 3: Check actual counts of potential candidates in temp[]*/ 
    for (int i=0; i<k-1; i++) 
    { 
     // Calculate actual count of elements 
     int ac = 0; // actual count 
     for (int j=0; j<n; j++) 
      if (arr[j] == temp[i].e) 
       ac++; 

     // If actual count is more than n/k, then print it 
     if (ac > n/k) 
      cout << "Number:" << temp[i].e 
       << " Count:" << ac << endl; 
    } 
} 

/* Driver program to test above function */ 
int main() 
{ 
    cout << "First Test\n"; 
    int arr1[] = {4, 5, 6, 7, 8, 4, 4}; 
    int size = sizeof(arr1)/sizeof(arr1[0]); 
    int k = 3; 
    moreThanNdK(arr1, size, k); 

    cout << "\nSecond Test\n"; 
    int arr2[] = {4, 2, 2, 7}; 
    size = sizeof(arr2)/sizeof(arr2[0]); 
    k = 3; 
    moreThanNdK(arr2, size, k); 

    cout << "\nThird Test\n"; 
    int arr3[] = {2, 7, 2}; 
    size = sizeof(arr3)/sizeof(arr3[0]); 
    k = 2; 
    moreThanNdK(arr3, size, k); 

    cout << "\nFourth Test\n"; 
    int arr4[] = {2, 3, 3, 2}; 
    size = sizeof(arr4)/sizeof(arr4[0]); 
    k = 3; 
    moreThanNdK(arr4, size, k); 

    return 0; 
} 

Answer 2

Tôi không chắc chắn 100%, nhưng nó có vẻ như bạn muốn giải quyết the Britney Spears problem — tìm một mục tạo nên một phần nhất định của một mẫu bằng bộ nhớ không đổi.

Đây là một tuyên bố về vấn đề bằng tiếng Anh, với một bản phác thảo của giải pháp:

& hellip; từ một bài báo năm 2002 của Erik D. Demaine của MIT và Alejandro López-Ortiz và J. Ian Munro của Đại học Waterloo ở Canada. Demaine và các đồng nghiệp của ông đã mở rộng các thuật toán để trang trải một vấn đề hơn tổng : Cho một dòng có độ dài n, xác định một tập hợp các kích thước m bao gồm tất cả các yếu tố xảy ra với tần suất lớn hơn hơn n/(m +1). (Trong trường hợp m = 1, điều này giảm xuống vấn đề đa số.) Thuật toán mở rộng yêu cầu m đăng ký cho các thành phần ứng viên cũng như bộ đếm m. Lược đồ hoạt động cơ bản tương tự như của thuật toán đa số. Khi một phần tử luồng khớp với một trong các ứng viên , bộ đếm tương ứng được tăng lên; khi không có trận đấu cho bất kỳ ứng cử viên nào, tất cả các quầy đều bị giảm; nếu bộ đếm ở 0, , ứng cử viên được liên kết sẽ được thay thế bởi một phần tử mới từ luồng.

Answer 3

Thuật toán O (n) đơn giản sẽ là giữ bản đồ băm từ số được tìm thấy cho số lượng các thể hiện được tìm thấy. Sử dụng một bản đồ băm là rất quan trọng để duy trì O (n). Các, một vượt qua cuối cùng trên bản đồ sẽ tiết lộ câu trả lời. Pass này cũng là O (n) vì kịch bản trường hợp xấu nhất là mỗi phần tử chỉ xuất hiện một lần và do đó bản đồ có cùng kích thước với mảng ban đầu.

Answer 4

Tôi không biết liệu bạn có bị hạn chế về cấu trúc dữ liệu bổ sung nào bạn có thể sử dụng hay không.

Điều gì về việc tạo một hashmap với 'elements' < -> count mapping. Chèn là O (log N). Tra cứu là O (1). Đối với mỗi phần tử, tra cứu trên hashtable, chèn nếu không tồn tại với số lượng 1. Nếu tồn tại, hãy kiểm tra nếu đếm < (n/k). Nó sẽ ở lại O (n).

EDIT:

Tôi quên giới hạn bộ nhớ không đổi. Đó là preallocating mục bản đồ băm với N yếu tố cho phép?

Answer 5

Có hai chung (lý thuyết) cách tiếp cận vấn đề này trong thời gian O (n)

I) Ý tưởng đầu tiên là đơn giản nhất

Bước 1) Trong khi có hơn k yếu tố riêng biệt, Chọn k các yếu tố riêng biệt và xóa tất cả chúng.

Bước 2) Kiểm tra tất cả các yếu tố còn lại k riêng biệt cho nó tần

Bằng chứng về tính đúng đắn: Lưu ý rằng khi bước sẽ được thực hiện ở hầu hết các n/k - 1 lần. Giả sử có một phần tử tự lặp lại ít nhất n/k lần. Trong trường hợp xấu nhất, nó có thể được chọn trong tất cả các lần lặp n/k-1 và nó vẫn sẽ nằm trong mảng cuối cùng sau khi nó được kiểm tra, nó sẽ được tìm thấy.

Triển khai: Bước 1 có thể được triển khai giữ một mảng liên kết (ánh xạ khóa tới giá trị) có kích thước k-1 (hằng số), bạn quét từ trái sang phải trên mảng, nếu bạn tìm thấy phần tử đã có trên bản đồ, tăng số lượt truy cập lên 1, nếu phần tử không có trên bản đồ và bản đồ chưa đầy (ít hơn k-1 phần tử), thêm phần tử mới này với số đếm ban đầu 1, nếu bản đồ đầy, xóa 1 khỏi bộ đếm của mỗi phần tử, nếu bất kỳ phần tử nào đạt 0, hãy xóa nó khỏi bản đồ. Cuối cùng, các phần tử trên bản đồ này sẽ tương đương với các phần tử còn lại bạn cần kiểm tra. Nếu, trong lần lặp cuối cùng bản đồ của bạn trở nên trống rỗng, bạn cần phải kiểm tra tất cả các phần tử trước khi xóa để bao gồm trường hợp tần số chính xác là n/k.

Mức độ phức tạp: Xem xét cách tiếp cận tồi tệ nhất cho bản đồ này, O (n * k) = O (n), như k là contant.

Bước 2 có thể được thực hiện bằng cách đếm tần số của tất cả (tối đa) k-1 yếu tố phức tạp: O (k * n) = O (n)

Nhìn chung phức tạp: O (n) + O (n) = O (n). (có một chi tiết nhỏ khác với triển khai, sự khác biệt của 1 phần tử, điều này xảy ra vì chúng tôi cũng muốn bao gồm trường hợp tần số chính xác n/k lặp lại trong mã giả, nếu không, chúng tôi có thể cho phép thêm một lần lặp lại có thể có chính xác k các phần tử khác nhau, không nhất thiết quá k)

II) Thuật toán thứ hai sử dụng thuật toán chọn trong thời gian tuyến tính http://en.wikipedia.org/wiki/Selection_algorithm và thuật toán phân vùng cũng chạy trong thời gian tuyến tính. Sử dụng chúng, bạn phá vỡ mảng của mình trong các nhóm k-1, với bất biến là bất kỳ phần tử nào trong nhóm thứ i nhỏ hơn hoặc bằng bất kỳ phần tử nào trong nhóm thứ j cho j> i trong O (n). Nhưng lưu ý rằng các yếu tố không được sắp xếp bên trong mỗi nhóm.

Bây giờ, bạn sử dụng thực tế là mỗi nhóm có phần tử n/(k-1) và bạn đang tìm kiếm một phần tử tự lặp lại ít nhất (n/k) và (n/k)> n/(2 * (k-1)). Điều này đủ để sử dụng định lý đa số, trong đó nói rằng nếu một phần tử là đa số (thường xuyên hơn số phần tử chia cho 2), thì nó cũng là trung bình của mảng. Bạn có thể lấy lại trung bình bằng thuật toán lựa chọn. Vì vậy, bạn chỉ cần kiểm tra tất cả trung bình và tất cả các trục cho các phân vùng, bạn cần kiểm tra chúng vì chúng có thể chia các giá trị bằng nhau trong hai nhóm khác nhau, có giá trị k-1 + k, độ phức tạp O ((2 *). k-1) * n)) = O (n).

Answer 6

này được thực hiện của tôi về thuật toán Jerky mô tả ở trên:

#include <map> 
#include <vector> 
#include <iostream> 
#include <algorithm> 

std::vector<int> repeatingElements(const std::vector<int>& a, int k) 
{ 
    if (a.empty()) 
     return std::vector<int>(); 

    std::map<int, int> candidateMap; //value, count; 

    for (int i = 0; i < a.size(); i++) 
    { 
     if (candidateMap.find(a[i]) != candidateMap.end()) 
     { 
      candidateMap[a[i]]++; 
     } 
     else 
     { 
      if (candidateMap.size() < k-1) 
      { 
       candidateMap[a[i]] = 1; 
      } 
      else 
      { 
       for (std::map<int, int>::iterator iter = candidateMap.begin(); 
        iter != candidateMap.end();) 
       { 
        (iter->second)--; 

        if (iter->second == 0) 
        { 
         iter = candidateMap.erase(iter); 
        } 
        else 
        { 
         iter++; 
        } 
       } 
      } 
     } 
    } 

    std::vector<int> ret; 

    for (std::map<int, int>::iterator iter = candidateMap.begin(); 
     iter != candidateMap.end(); iter++) 
    { 
     int candidate = iter->first; 

     if (std::count(a.begin(), a.end(), candidate) > (a.size()/k)) 
     { 
      ret.push_back(candidate); 
     } 
    } 

    return ret; 
} 

int main() 
{ 
    std::vector<int> a = { 1, 1, 4, 2, 2, 3, 3 }; 
    int k = 4; 

    std::vector<int> repeating_elements = repeatingElements(a, k); 

    for (int elem : repeating_elements) 
    { 
     std::cout << "Repeating more than n/" << k << " : " << elem << std::endl; 
    } 

    return 0; 
} 

Và kết quả là:

Lặp đi lặp lại hơn n/4: 1

Lặp đi lặp lại hơn n/4: 2

Lặp lại nhiều hơn n/4: 3