Cách tốt nhất để tìm vị trí của phần tử trong mảng chưa phân loại sau khi được sắp xếp

Question

Chúng tôi có mảng chưa phân loại, cần in vị trí của mỗi phần tử giả định rằng nó được sắp xếp.

ví dụ .: chúng tôi có một mảng.

arr[] = {3, 2, 6, 1, 4} 
//index: 1 2 3 4 5 Index of elements 1-based 

//Sorted {1, 2, 3, 4, 6} List after sorting 
//index: 4 2 1 5 3 Index of elements from original array 

nó nên in

Answer 1

Sắp xếp mảng {1, 2, 3, ..., N} song song với mảng nhất định. Vì vậy, trong ví dụ của bạn, {3, 2, 6, 4} sẽ được sắp xếp, với mỗi lần hoán đổi ảnh hưởng đến mảng đó và mảng {1, 2, 3, 4}. Kết quả cuối cùng sẽ là {2, 3, 4, 6} cho mảng đầu tiên và {2, 1, 4, 3} cho mảng thứ hai; mảng thứ hai là câu trả lời cho câu hỏi của bạn.

Trong trường hợp đó không phải là rõ ràng, đây là một ví dụ nữa:

5 2 1 4 3 
1 2 3 4 5 

2 5 1 4 3 
2 1 3 4 5 

2 1 5 4 3 
2 3 1 4 5 

2 1 4 5 3 
2 3 4 1 5 

2 1 4 3 5 
2 3 4 5 1 

2 1 3 4 5 
2 3 5 4 1 

1 2 3 4 5 
3 2 5 4 1 

tôi đã sử dụng bong bóng sắp xếp :-) để sắp xếp hàng đầu tiên, và chỉ cần hoán đổi hàng dưới cùng song song với dòng đầu tiên. Nhưng ý tưởng nên làm việc với bất kỳ phương pháp phân loại nào: chỉ cần thao tác hàng dưới cùng song song với các thao tác (hoán đổi hoặc bất kỳ thứ gì) mà bạn đang thực hiện ở hàng trên cùng.

Answer 2

Bạn có thể tạo một mảng perm, giữ chỉ số của mảng đầu tiên arr, và sắp xếp perm mảng này dựa trên giá trị của arr

int arr[] = {3, 2, 6, 4}; 

int compare (const void * a, const void * b) { 
    int diff = arr[*(int*)a] - arr[*(int*)b]; 
    return diff; 
} 

int main(void) { 
    int perm[4], i; 

    for (i = 0 ; i != 4 ; i++) { 
     perm[i] = i ; 
    } 
    qsort (perm, 4, sizeof(int), compare); 

    for (i = 0 ; i != 4 ; i++) { 
     printf("%d ", perm[i] + 1); 
    } 
    return 0; 
} 

Output:

2 1 4 3 

Liên kết http://ideone.com/wH1giv

Answer 3

Lưu trữ dữ liệu và chỉ mục của phần tử mảng dưới dạng một cặp và sắp xếp mảng các cặp. Bây giờ chỉ in phần chỉ mục.

// Original array 
int arr[] = {3, 2, 6, 4}; 
// Size of original array 
const int sz = static_cast<int>(sizeof arr/sizeof arr[0]); 
// Array of pair {.first = item, .second = 1-based index 
std::vector< pair<int, int> > vp(sz); // std::array if size is fixed 
for(int i = 0; i < sz; ++i) vp[i] = make_pair(arr[i], i + 1); /* Can be done in a more fancy way using std::transform + lambda */ 
// Sort the array, original array remains unchanged 
std::sort(vp.begin(), vp.end()); 
// Print the result 
for(int i = 0; i < sz; ++i) cout << ' ' << vp[i].second; 

Live code

Thời gian phức tạp của mã: O (N log N) trong đó N là số phần tử trong mảng

---

Từ bạn nhận xét như giá trị của N lớn và tất cả các số khác nhau, bạn có thể sử dụng đoạn mã sau

int maxn = maximum value of a number; 
int positions[maxn] = {0}; // Or choose a sparse array with constant update time 
int arr[] = {3, 2, 6, 4}; 
const int sz = static_cast<int>(sizeof arr/sizeof arr[0]); 
for(int i = 0; i < sz; ++i) { 
    assert(arr[i] >= 0); 
    position[ arr[i] ] = i + 1; 
} 

for(int i = 0; i < maxn; ++i) { 
    if(position[i]) cout << ' ' << position[i]; 
} 

Live code

Thời gian phức tạp của mã: O (N) trong đó N là giá trị lớn nhất của số

Answer 4

Tôi không biết C++, vì vậy tôi không thể cung cấp cho bạn mã chính xác, nhưng bên dưới mã giả nên hoạt động.

1. Given input array 
2. Take another empty array of equal length (This will be the output array of positions) 
3. Fill the output array with zero (initially all values will be zero in the array) 
4. while (output array does not contain zero) 
    a. loop through input array and find maximum number in it. 
    b. get the position of maximum number from input array and set it at the same position in output array 
    c. ignore the element in input array ,if corresponding index in output array is not zero (if it is not zero, then it means index is already filled up) 
5. Repeat setps a,b and c until all the elements in output array becomes non zero 

Độ phức tạp của thuật toán này là O (n2). Tôi không tìm được cách nào tốt hơn thế này. Vui lòng cho tôi biết nếu bạn có bất kỳ thắc mắc nào.

Answer 5

Tôi không biết đó là cách hiệu quả nhất nhưng tôi sẽ tạo một array of nodes. Mỗi node có value và pos. Sau đó, sắp xếp theo giá trị mà từ đó bạn có thể truy lục vị trí.

struct node{ 
    int value; 
    int pos; 
} 

Như tôi đã nói, nó sẽ làm việc nhưng tôi nghi ngờ nó là cách hiệu quả nhất

Answer 6

Bạn có thể sử dụng như sau:

template <typename T> 
std::vector<std::size_t> compute_ordered_indices(const std::vector<T>& v) 
{ 
    std::vector<std::size_t> indices(v.size()); 
    std::iota(indices.begin(), indices.end(), 0u); 
    std::sort(indices.begin(), indices.end(), [&](int lhs, int rhs) { 
     return v[lhs] < v[rhs]; 
    }); 
    return indices; 
} 

Live Demo