我有以下数组：
{7,1,3,9,5,4,7,8,2}
和一个空的n大小的数组。现在，我想在给定数组中查找n个最小值的索引而不进行排序，并将它们写入空数组。例如n = 3：
{1,2}
有一种简单的方法吗？
tpl1123 回答：在不排序的情况下找到数组中n个最小值的索引
如果不限制对 other 数组进行排序，则创建索引数组，并根据原始数组对索引数组进行排序。
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
int main()
{
int n = 3;
// test data
std::vector<int> test = { 7,1,3,9,5,4,7,8,2 };
// index array
std::vector<int> index(test.size());
// set the index array to 0,2,… n-1
std::iota(index.begin(),index.end(),0);
// sort the index array
std::sort(index.begin(),[&](int n1,int n2) { return test[n1] < test[n2]; });
// output results -- note we are printing the index array
for (int i = 0; i < n; ++i)
std::cout << index[i] << "\n";
}
输出：
1
8
2
从数组中的第一个值开始。
比较数组中的值和n-least数组中的索引值。 （如果为空，则将其添加）。
如果该值较小，则将数组从该位置移开，然后将索引添加到n-least数组中的该位置。
如果不小于该值，则比较n-least数组中的下一个值，依此类推。
这可能不是最佳选择，但至少没有幼稚的解决方案会产生O（n ^ 2）复杂性。
我将用伪代码编写它：
n = 3
arr = [7,2]
narr = []
for i as 0 to sizeof(arr) - 1
for j as 0 to n - 1
if narr[j] is undefined or arr[i] < arr[narr[j]]
narr.shiftRight(j,1)
narr[j] = i;
break
endif
endfor
endfor