chỉ số của k phần tử lớn nhất trong một mảng có chiều dài không phân loại

Question

Tôi cần tìm các chỉ số của k phần tử lớn nhất của một unsorted, length n, array/vector trong C++, với k < n. Tôi đã thấy cách sử dụng nth_element() để tìm số liệu thống kê thứ k, nhưng tôi không chắc liệu đây có phải là sự lựa chọn đúng đắn cho vấn đề của tôi vì có vẻ như tôi cần phải gọi k tới nth_statistic, mà tôi đoán nó sẽ có độ phức tạp O (kn), mà có thể tốt như nó có thể nhận được? Hoặc là có một cách để làm điều này chỉ trong O (n)?

Thực hiện nó mà không có nth_element() có vẻ như tôi sẽ phải lặp lại toàn bộ mảng một lần, điền vào danh sách các chỉ mục của các phần tử lớn nhất ở mỗi bước.

Có điều gì trong thư viện C++ chuẩn làm cho một lớp lót này trở thành một lớp hay cách thông minh để thực hiện điều này chỉ trong một vài dòng? Trong trường hợp cụ thể của tôi, k = 3, và n = 6, vì vậy hiệu quả không phải là một mối quan tâm lớn, nhưng nó sẽ là tốt đẹp để tìm một cách sạch sẽ và hiệu quả để làm điều này cho k tùy ý và n.

Có vẻ như Mark the top N elements of an unsorted array có lẽ là bài đăng gần nhất tôi có thể tìm thấy trên SO, các bài đăng có bằng Python và PHP.

Answer 1

Bạn có thể sử dụng cơ sở thuật toán quicksort để thực hiện những gì bạn cần, ngoại trừ thay vì sắp xếp lại các phân vùng, bạn có thể loại bỏ các mục nằm ngoài phạm vi mong muốn.

Nó được gọi là "nhanh chóng chọn" và here is a C++ implementation:

int partition(int* input, int p, int r) 
{ 
    int pivot = input[r]; 

    while (p < r) 
    { 
     while (input[p] < pivot) 
      p++; 

     while (input[r] > pivot) 
      r--; 

     if (input[p] == input[r]) 
      p++; 
     else if (p < r) { 
      int tmp = input[p]; 
      input[p] = input[r]; 
      input[r] = tmp; 
     } 
    } 

    return r; 
} 

int quick_select(int* input, int p, int r, int k) 
{ 
    if (p == r) return input[p]; 
    int j = partition(input, p, r); 
    int length = j - p + 1; 
    if (length == k) return input[j]; 
    else if (k < length) return quick_select(input, p, j - 1, k); 
    else return quick_select(input, j + 1, r, k - length); 
} 

int main() 
{ 
    int A1[] = { 100, 400, 300, 500, 200 }; 
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl; 
    int A2[] = { 100, 400, 300, 500, 200 }; 
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl; 
    int A3[] = { 100, 400, 300, 500, 200 }; 
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl; 
    int A4[] = { 100, 400, 300, 500, 200 }; 
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl; 
    int A5[] = { 100, 400, 300, 500, 200 }; 
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl; 
} 

OUTPUT:

1st order element 100 
2nd order element 200 
3rd order element 300 
4th order element 400 
5th order element 500 

EDIT

Đó thực hiện cụ thể có một O (n) trung bình thời gian chạy; do phương pháp lựa chọn trục, nó chia sẻ thời gian chạy trường hợp xấu nhất của quicksort. Bởi optimizing the pivot choice, trường hợp xấu nhất của bạn cũng trở thành O (n).

Answer 2

Thư viện chuẩn sẽ không giúp bạn có được danh sách các chỉ mục (nó đã được thiết kế để tránh truyền tải dữ liệu dư thừa). Tuy nhiên, nếu bạn quan tâm đến n yếu tố lớn nhất, sử dụng một số loại phân vùng (cả std::partition và std::nth_element là O (n)):

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

struct Pred { 
    Pred(int nth) : nth(nth) {}; 
    bool operator()(int k) { return k >= nth; } 
    int nth; 
}; 

int main() { 

    int n = 4; 
    std::vector<int> v = {5, 12, 27, 9, 4, 7, 2, 1, 8, 13, 1}; 

    // Moves the nth element to the nth from the end position. 
    std::nth_element(v.begin(), v.end() - n, v.end()); 

    // Reorders the range, so that the first n elements would be >= nth. 
    std::partition(v.begin(), v.end(), Pred(*(v.end() - n))); 

    for (auto it = v.begin(); it != v.end(); ++it) 
     std::cout << *it << " "; 
    std::cout << "\n"; 

    return 0; 
} 

Answer 3

Đây là thực hiện của tôi mà những gì tôi muốn và tôi nghĩ là hợp lý hiệu quả:

#include <queue> 
#include <vector> 
// maxindices.cc 
// compile with: 
// g++ -std=c++11 maxindices.cc -o maxindices 
int main() 
{ 
    std::vector<double> test = {0.2, 1.0, 0.01, 3.0, 0.002, -1.0, -20}; 
    std::priority_queue<std::pair<double, int>> q; 
    for (int i = 0; i < test.size(); ++i) { 
    q.push(std::pair<double, int>(test[i], i)); 
    } 
    int k = 3; // number of indices we need 
    for (int i = 0; i < k; ++i) { 
    int ki = q.top().second; 
    std::cout << "index[" << i << "] = " << ki << std::endl; 
    q.pop(); 
    } 
} 

mang đến cho đầu ra:

index[0] = 3 
index[1] = 1 
index[2] = 0 

Answer 4

câu hỏi đặt ra có câu trả lời từng phần; đó là std::nth_element trả về "số liệu thống kê thứ n" với thuộc tính không có phần tử nào đứng trước thứ n lớn hơn và không có yếu tố nào sau đây ít hơn.

Do đó, chỉ một cuộc gọi đến std::nth_element là đủ để có được k thành phần lớn nhất. Độ phức tạp về thời gian sẽ là O (n) về lý thuyết nhỏ nhất vì bạn phải truy cập từng phần tử ít nhất một lần để tìm phần tử nhỏ nhất (hoặc trong trường hợp này k-nhỏ nhất). Nếu bạn cần những phần tử k này, bạn cần phải đặt chúng là O (k log (k)). Vì vậy, trong tổng số O (n + k log (k)).

Answer 5

này phải là một phiên bản cải tiến của @hazelnusse được thực hiện trong O(nlogk) thay vì O(nlogn)

#include <queue> 
#include <iostream> 
#include <vector> 
// maxindices.cc 
// compile with: 
// g++ -std=c++11 maxindices.cc -o maxindices 
int main() 
{ 
    std::vector<double> test = {2, 8, 7, 5, 9, 3, 6, 1, 10, 4}; 
    std::priority_queue< std::pair<double, int>, std::vector< std::pair<double, int> >, std::greater <std::pair<double, int> > > q; 
    int k = 5; // number of indices we need 
    for (int i = 0; i < test.size(); ++i) { 
    if(q.size()<k) 
     q.push(std::pair<double, int>(test[i], i)); 
    else if(q.top().first < test[i]){ 
     q.pop(); 
     q.push(std::pair<double, int>(test[i], i)); 
    } 
    } 
    k = q.size(); 
    std::vector<int> res(k); 
    for (int i = 0; i < k; ++i) { 
    res[k - i - 1] = q.top().second; 
    q.pop(); 
    } 
    for (int i = 0; i < k; ++i) { 
    std::cout<< res[i] <<std::endl; 
    } 
} 

Answer 6

Bạn có thể làm điều này trong O(n) thời gian với một lần tính toán thống kê đơn hàng:

• Hãy r được thống kê k trật tự -thứ
• Initialize hai danh sách rỗng bigger và equal.
• Đối với mỗi chỉ số i:
  • Nếu array[i] > r, thêm i-bigger
  • Nếu array[i] = r, thêm i để equal
• yếu tố Huỷ từ equal cho đến khi tổng các độ dài của hai danh sách là k
• Trả lại kết nối của hai danh sách.

Đương nhiên, bạn chỉ cần một danh sách nếu tất cả các mục là khác biệt. Và nếu cần thiết, bạn có thể thực hiện các thủ thuật để kết hợp hai danh sách thành một, mặc dù điều đó sẽ làm cho mã phức tạp hơn.

Answer 7

Mặc dù đoạn mã sau có thể không đáp ứng các ràng buộc phức tạp mong muốn, nó có thể là một lựa chọn thú vị cho hàng đợi ưu tiên đã đề cập trước đó.

#include <queue> 
#include <vector> 
#include <iostream> 
#include <iterator> 
#include <algorithm> 

std::vector<int> largestIndices(const std::vector<double>& values, int k) { 
    std::vector<int> ret; 

    std::vector<std::pair<double, int>> q; 
    int index = -1; 
    std::transform(values.begin(), values.end(), std::back_inserter(q), [&](double val) {return std::make_pair(val, ++index); }); 
    auto functor = [](const std::pair<double, int>& a, const std::pair<double, int>& b) { return b.first > a.first; }; 
    std::make_heap(q.begin(), q.end(), functor); 
    for (auto i = 0; i < k && i<values.size(); i++) { 
     std::pop_heap(q.begin(), q.end(), functor); 
     ret.push_back(q.back().second); 
     q.pop_back(); 
    } 

    return ret; 
} 

int main() 
{ 
    std::vector<double> values = { 7,6,3,4,5,2,1,0 }; 
    auto ret=largestIndices(values, 4); 
    std::copy(ret.begin(), ret.end(), std::ostream_iterator<int>(std::cout, "\n")); 
}