首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >创建未排序数组的索引的最快方法

创建未排序数组的索引的最快方法
EN

Stack Overflow用户
提问于 2015-06-07 11:46:22
回答 4查看 722关注 0票数 2

我正在处理一个问题,其中我有一个未排序的数组。我需要处理这个数组,以便生成一个索引数组,就像它按升序排序一样。

示例1:

假设我有一个未排序的数组9,7,8,6,12

作为输出,我需要一个索引数组3、1、2、0、4。

示例2:

未排序数组: 10、9、11、8、12索引数组应该是: 2、1、3、0、4

到目前为止,我就像以前的“泡泡分类”一样,在比较每一种可能性。我在想怎么快点。

EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2015-06-07 11:53:08

如果您不担心额外的空间,请执行以下操作:

  1. 制作成对数组( (value, index) )
  2. 按升序对值(第一个成员)排序
  3. 从排序的对数组中获取索引(第二个成员)

以您的数据为例,您将得到以下内容:

代码语言:javascript
代码运行次数:0
运行
复制
[{9,0}, {7,1}, {8,2}, {6,3}, {12,4}] // Step 1
[{6,3}, {7,1}, {8,2}, {9,0}, {12,4}] // Step 2
[   3,     1,     2,     0,      4 ] // Step 3

(注释)我需要的是未排序数组的索引,就好像它们是按升序排序的一样。

您也可以使用步骤3中的数组来生成此输出。使用第二个例子,您可以得到以下内容:

代码语言:javascript
代码运行次数:0
运行
复制
[{10,0},  {9,1}, {11,2},  {8,3}, {12,4}]
[ {8,3},  {9,1}, {10,0}, {11,2}, {12,4}]
[    3,      1,      0,      2,      4 ]

现在创建输出数组,遍历索引数组(即[3,1,0,2,4]),并将每个项的索引设置到由值确定的结果中的位置,即索引3将得到0,因为3位于索引0,索引1将得到1,因为1在1,索引0将得到2,因为0在2,依此类推。

下面是这一额外步骤的说明:

代码语言:javascript
代码运行次数:0
运行
复制
int position[] = {3, 1, 0, 2, 4};
int res[5];
for (int i = 0 ; i != 5 ; i++) {
    res[position[i]] = i;
}

这将产生以下数组:

代码语言:javascript
代码运行次数:0
运行
复制
[2, 1, 3, 0, 4]
票数 5
EN

Stack Overflow用户

发布于 2015-06-07 11:52:18

“快速”意味着插入(当然还有查找)需要一个复杂度为O(log )的排序数据结构。所以二叉树就行了。

票数 1
EN

Stack Overflow用户

发布于 2015-06-07 11:54:06

您可以将索引创建为一个位置数组,并按照现有顺序初始化它: idx=0,1,2,.,n-1。

然后使用您最喜欢的排序算法对索引数组进行排序,但是每当执行比较时,您都会使用这些值作为引用原始数组的位置,而不是直接比较它们。例如,要比较项目i和j,可以执行cmp(arr[idxi],arr[idxj])而不是cmp(idxi,idxj)。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30693139

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档