在排序之后找到未排序数组中元素位置的最佳方法

Question

我们有一个未排序的数组,需要打印每个元素的位置,假设它被排序.

例如:我们有一个数组.

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

它应该打印

4 2 1 5 3

Answer 1

{1, 2, 3, ..., N}与给定数组并行对数组进行排序.因此,在您的示例中,{3, 2, 6, 4}将对每个交换影响该数组和数组进行排序{1, 2, 3, 4}.最终结果将是{2, 3, 4, 6}第一个数组和{2, 1, 4, 3}第二个数组; 后一个数组就是你问题的答案.

如果不清楚,这是一个较长的例子:

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

我使用冒泡排序:-)对顶行进行排序,并将底行与顶行平行交换.但是这个想法应该适用于任何排序方法:只需与你在顶行执行的操作(交换或其他)并行操作底行.