Cách lấy chỉ số hoán vị sau khi sắp xếp

Question

Cho một mảng arr = {5, 16, 4, 7}, chúng tôi có thể sắp xếp nó qua sort(arr, arr+sizeof(arr)/sizeof(arr[0])). vì vậy bây giờ mảng arr = {4, 5, 7, 16} và chỉ mục hoán vị cho mảng được sắp xếp là {2, 0, 3, 1}. Nói cách khác, arr[2] trong mảng ban đầu bây giờ là phần tử nhỏ nhất trong mảng được sắp xếp ở vị trí 0.

Có cách nào hiệu quả để chúng tôi có thể nhận chỉ mục hoán vị không?

Cảm ơn bạn

Answer 1

Tạo một mảng các chỉ mục, điền vào các số đó bằng 0.N-1 và sắp xếp nó bằng bộ so sánh tùy chỉnh. Bộ so sánh phải so sánh các mục từ mảng gốc tại các chỉ mục lhs và rhs. Sắp xếp mảng các chỉ số theo cách này sắp xếp lại chúng như là một hoán vị:

vector<int> data = {5, 16, 4, 7}; 
vector<int> index(data.size(), 0); 
for (int i = 0 ; i != index.size() ; i++) { 
    index[i] = i; 
} 
sort(index.begin(), index.end(), 
    [&](const int& a, const int& b) { 
     return (data[a] < data[b]); 
    } 
); 
for (int i = 0 ; i != index.size() ; i++) { 
    cout << index[i] << endl; 
} 

này in 2, 0, 3, 1

Đây là một demo on ideone.

Lưu ý: bạn có thể sử dụng index để lấy data theo thứ tự sắp xếp:

for (int i = 0 ; i != index.size() ; i++) { 
    cout << data[index[i]] << endl; 
} 

Answer 2

Tại sao không đặt một số dữ liệu vệ tinh? Thay vì phân loại các con số, chỉ cần sắp xếp các cặp số và chỉ số của chúng. Vì việc sắp xếp được thực hiện lần đầu tiên trên phần tử đầu tiên của cặp, điều này sẽ không làm gián đoạn thuật toán phân loại ổn định.

Đối với các thuật toán không ổn định, điều này sẽ thay đổi thuật toán thành ổn định.

Nhưng lưu ý rằng nếu bạn cố gắng phân loại theo cách này, nó sẽ tạo chỉ mục trong khi sắp xếp, không phải sau đó.

Ngoài ra, vì biết chỉ mục hoán vị sẽ dẫn đến thuật toán sắp xếp O (n), nên bạn không thể thực hiện nhanh hơn O (nlogn).

Answer 3

Vâng, có một với O(NlogN) time.Since việc phân loại mất O(NlogN) thời gian dù sao, điều này sẽ không ảnh hưởng đến độ phức tạp thời gian tổng thể.
Thời gian phức tạp: O(NlogN)
Space phức tạp: O(N)
nơi N = số phần tử trong mảng đầu vào

Thuật toán:

1. Make bản sao của mảng đầu vào (P) gọi nó là Q.
2. Sor t đầu vào mảng P.
3. Đối với mỗi số trong Q, làm tìm kiếm nhị phân để tìm chỉ số của nguyên tố đó trong P.

Answer 4

Vâng trong C++ chúng ta có thể sử dụng cặp datatype để làm điều này một cách dễ dàng. Mã mẫu dưới đây;

arr = {5, 16, 4, 7}; 
vector<pair<int,int> >V; 
for(int i=0;i<4;i++){ 
    pair<int,int>P=make_pair(arr[i],i); 
    V.push_back(P); 
} 

sort(V.begin(),V.end()); 

Vì vậy, V [i].đầu tiên là giá trị thứ i và V [i] .second là chỉ số thứ i. Vì vậy, để in chỉ mục trong mảng được sắp xếp.

for(int i=0;i<4;i++)cout<<V[i].second<<endl; 

Lưu ý rằng khi sắp xếp mảng (hoặc vectơ) của các mục ghép đôi, mảng được sắp xếp đầu tiên dựa trên giá trị đầu tiên. Nếu hai cặp có cùng giá trị đầu tiên thì chúng được sắp xếp dựa trên giá trị thứ hai của chúng.

Answer 5

Multimap có thể đến để giải cứu

template<typename TIn, typename TOut> 
sortindex(const TIn &first, const TIn &last, TOut &out) { 
    using ValT = typename std::decay<decltype(*first)>::type; 
    std::multimap<ValT, size_t> sindex; 

    for(auto p=first; p != last; p++) 
     sindex.emplace(*p, std::distance(first, p)); 

    for(auto &&p: sindex) 
     *out++ = p.second; 
} 

mà có thể được sử dụng như thế này:

std::vector<size_t> a{32, 22, 45, 9, 12, 15}; 
std::vector<size_t> indexes; 

sortindex(a.begin(), a.end(), std::back_inserter(indexes)); 

Nếu một khớp nối giữa các giá trị được sắp xếp và chỉ số sẽ được cần, thì Multimap có thể được trả về trực tiếp, thay vì viết các chỉ mục cho trình vòng lặp đầu ra.

template<typename TIn> 
auto 
sortindex(const TIn &first, const TIn &last) 
    --> std::multimap<typename std::decay<decltype(*first)>::type, size_t> 
{ // return value can be commented out in C++14 
    using ValT = typename std::decay<decltype(*first)>::type; 
    std::multimap<ValT, size_t> sindex; 

    for(auto p=first; p != last; p++) 
     sindex.emplace(*p, std::distance(first, p)); 

    return sindex; 
} 

Answer 6

Gần đây, tôi đã phải giải quyết một vấn đề tương tự trong PHP. Bạn tạo một hàm so sánh cục bộ để được sử dụng bởi thuật toán sắp xếp UASORT của PHP. Gọi array_keys() trên mảng đã sắp xếp, và nó sẽ nhổ ra mảng hoán vị của bạn.

// test mảng

$ tArray = array ('2', '10', '1', '23', '8', '3');

// sắp xếp mảng; để duy trì liên kết chỉ mục, sử dụng uasort; khác sử dụng usort, v.v.

uasort ($ tArray, 'compareSize');

// các phím kết quả là chỉ số hoán vị của bạn (nếu uasort sử dụng trong bước trước)

$ Phím = array_keys ($ tArray);

// địa phương so sánh chức năng

chức năng compareSize ($ a, $ b) {

if ($ a == $ b) {return 0; } else {return ($ a < $ b)? -1: 1; }

}

======================================== =============================== Kết quả:

được sắp xếp =: Array ([2] => 1 [ 0] => 2 [5] => 3 [4] => 8 [1] => 10 [3] => 23)

phím =: Array ([0] => 2 [1] => 0 [2] => 5 [3] => 4 [4] => 1 [5] => 3)

Answer 7

Tôi nghĩ rằng chúng ta có thể giải quyết vấn đề này mà không cần dùng vector. Tôi là người mới, thành thật mà nói, tôi không hiểu những gì bạn đã viết ở trên, và tất cả các bạn đã sử dụng véc tơ mà tôi sẽ học sau :)) (Tôi lười) Đây là cách của tôi:

// thứ nhất, mảng sao chép một [] để mảng b []

void copyarray(double b[],double a[],int n){ 
    for(int i=0;i<n;i++)b[i]=a[i]; 
    } 

// thứ hai, sắp xếp mảng a [] (giảm)

/* thứ ba, "sorter" mảng a [], mà có nghĩa là: trong mảng a [], nếu có cùng giá trị, chúng sẽ hợp nhất thành một giá trị! tôi sẽ thiết lập mảng o [] là "mảng được sắp xếp một []" */

void sorter(double o[],double a[],int n,int &dem){ 
    int i; 
    o[0]=a[0]; 
    for(i=1;i<n;i++){ 
     if(a[i]!=a[i-1]){ 
      dem++; o[dem]=a[i]; 
     } 
     } 
     dem++; 
} 

/* 4, mục tiêu chính của chúng tôi: có được các chỉ số: tôi sẽ đưa các chỉ số vào mảng c [] */

void index_sort(double o[],double b[], double c[], int dem, int n){ 
    int i,j,chiso=0; 
    for(j=0;j<dem;j++){ 
     for(i=0;i<n;i++){ 
      if(b[i]==o[j]){ 
      c[chiso]=i; 
      chiso++; 
      } 
     } 
    } 
} 

    // DONE! 
int main(){ 
     int n,dem=0; 
     double a[100],b[100],c[100],o[100]; 
     cin>>n; 
     input(a,n); 
     copyarray(b,a,n); 
     copyarray(c,a,n); 
     sort(a,n); 
     sorter(o,a,n,dem); 
     index_sort(o,b,c,dem,n); 
     for(int i=0;i<n;i++) cout<<c[i]<<" "; 
    }