求一个数组中最大的前n个数的下标
假设有一个数组，现求出数组中最大的前n个数的下标。
输入：一个数组 Input[]
输出：一个数组 Output[]
注意：
n是一个未知数。
Input中的数，很具有区分度，大小差别挺大。
Input中的数，有重复的。
例：
int Input[] ={1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 200, 12, 180, 190, 220, 221, 3, 5, 226};
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,18,19//这里是对应的坐标
public static int[] Compute(int Input[]){
}
输出
Ouput={11,13,14,15,16,19}
Output是较大的几个数对应的下标.
[解决办法]
用快速排序的partition方式，每次partition
用数组Pos[n],记录下标的变化：如j号位置和i号位交换，那么就把Pos[i]=j
其他的就和partition求出前M大元素一模一样
[解决办法]
用最小堆吧
[解决办法]
弄了好久,没做出来
[解决办法]
终于出来了
public class Test { public static void main(String args[]){ int Input[] ={1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 200, 12, 180, 190, 220, 221, 3, 5, 226}; // 对应的坐标 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 int out[] = Compute(Input); for (int i = 0; i < out.length; i++) { //Ouput={11,13,14,15,16,19} System.out.println(out[i]); } } public static int[] Compute(int Input[]){ int out[] = new int[5]; for (int i = 0; i < 5; i++) { int k = 0; for (int j = 0; j < Input.length; j++) { if (k < Input[j]) { k = Input[j]; out[i] = j; } } Input[out[i]] = 0; } return out; }}
[解决办法]
排序，nlogn,换位rank即可。
[解决办法]
从n个数中找最大的k个数
可以将下标和值放入一个struct里，然后找最大的k个
方法一：将其分成两堆，首先取一个数x,比x大放入sa，不比x大放入sb,若sa的个数大于k，则对sa再分。若sa的个数=k，则sa就是要找的那个。若sa的个数小于k，这k个是要找的，再从sb中用相同的方法找k-|sa|个。
代码：
//从n个数中查找最大的k个数，method1 //时间复杂度O(N*log(K)) #include<iostream>#include<vector>using namespace std;void f(int k,vector<int>& v,vector<int>& sa,vector<int>& sb){//v输入数组，sa比x大的数的数组，sb比x小的数组。 while(1){ int x=v[(int)(v.size()*((double)rand()/RAND_MAX))];//随机从vector v中找个数 for(int i=0;i<v.size();i++){ int tp=v[i]; if(tp>=x){//比x大就放到sa中，小就放到sb中 sa.push_back(tp); } else{ sb.push_back(tp); } } if(sa.size()>k){//如果sa的个数大于k，就从sa中找k个数 v=sa; sa.clear();sb.clear(); continue; } else{ if(sa.size()==k){//如果sa的个数等于k，就输出k个数 for(int i=0;i<sa.size();i++){ cout<<sa[i]<<" "; } cout<<endl;break; } else{ for(int i=0;i<sa.size();i++){//如果sa个数少于k个，就输出这|sa|个数，并从sb中找k-|sa|个数 cout<<sa[i]<<" "; } v=sb;k=k-sa.size(); sa.clear();sb.clear(); continue; } } } } void print(int i){ cout<<i<<" ";} int main(){ vector<int> v;int n; cout<<"input n"<<endl;cin>>n; for(int i=0;i<n;i++){//生成随机的n个数，范围是[0,99] int tp=rand()%100; v.push_back(tp); } for_each(v.begin(),v.end(),print);cout<<endl; //输出这些数 cout<<"input k\n"; int k;cin>>k; vector<int> sa,sb; f(k,v,sa,sb);//调用上面的函数 system("pause");}
[解决办法]
从n个数中找最大的k个数
可以将下标和值放入一个struct里，然后找最大的k个
方法一：将其分成两堆，首先取一个数x,比x大放入sa，不比x大放入sb,若sa的个数大于k，则对sa再分。若sa的个数=k，则sa就是要找的那个。若sa的个数小于k，这k个是要找的，再从sb中用相同的方法找k-|sa|个。
代码：
//从n个数中查找最大的k个数，method1 //时间复杂度O(N*log(K)) #include<iostream>#include<vector>using namespace std;void f(int k,vector<int>& v,vector<int>& sa,vector<int>& sb){//v输入数组，sa比x大的数的数组，sb比x小的数组。 while(1){ int x=v[(int)(v.size()*((double)rand()/RAND_MAX))];//随机从vector v中找个数 for(int i=0;i<v.size();i++){ int tp=v[i]; if(tp>=x){//比x大就放到sa中，小就放到sb中 sa.push_back(tp); } else{ sb.push_back(tp); } } if(sa.size()>k){//如果sa的个数大于k，就从sa中找k个数 v=sa; sa.clear();sb.clear(); continue; } else{ if(sa.size()==k){//如果sa的个数等于k，就输出k个数 for(int i=0;i<sa.size();i++){ cout<<sa[i]<<" "; } cout<<endl;break; } else{ for(int i=0;i<sa.size();i++){//如果sa个数少于k个，就输出这|sa|个数，并从sb中找k-|sa|个数 cout<<sa[i]<<" "; } v=sb;k=k-sa.size(); sa.clear();sb.clear(); continue; } } } } void print(int i){ cout<<i<<" ";} int main(){ vector<int> v;int n; cout<<"input n"<<endl;cin>>n; for(int i=0;i<n;i++){//生成随机的n个数，范围是[0,99] int tp=rand()%100; v.push_back(tp); } for_each(v.begin(),v.end(),print);cout<<endl; //输出这些数 cout<<"input k\n"; int k;cin>>k; vector<int> sa,sb; f(k,v,sa,sb);//调用上面的函数 system("pause");}