中兴笔试排序题求解答

#include<iostream> #include<vector> #include<algorithm> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int in[] = { 1, 1, 1, 1, 3, 3, 3, 4, 5, 2, 6, 6, 6, 6, 6 }; vector<pair<int, int>> test; for (int i = 0; i < sizeof(in) / sizeof(int); i++) { auto it = test.begin(); for (; it != test.end(); it++) { if (it->first == in[i]) { it->second++; break; } } if (it == test.end()) { test.push_back(make_pair(in[i], 1)); } } stable_sort(test.begin(), test.end(), [](pair<int, int> fr, pair<int, int> bc){return fr.second > bc.second; }); for (auto i = 0; i < test.size() - 1; i++) { for (int j = 0; j < test[i].second; j++) { cout << test[i].first << " "; } } if (test.size()>0) { for (int i = 0; i < test[test.size() - 1].second-1; i++) { cout << test[test.size() - 1].first << " "; } cout << test[test.size() - 1].first << endl; } return 0; } 用stable_sort就可以吧

//用lambda void Sortbytimes(vector<int> A) {  int len = A.size();  map<int, int> res;  for (int i = 0;i < len;i++)  {   auto ret = res.insert({ A[i],1 });   if (ret.second == false)    res[A[i]]++;  }  stable_sort(A.begin(), A.end(), [res](const int& a, const int& b) {return  res.at(a)>res.at(b);});;  for (auto a : A)   cout << a << " "; }

我只想到这种效率比较低的 import java.util.Arrays; import java.util.LinkedHashMap; import java.util.Scanner; import java.util.Set; public class Main {  public static void main(String[] args) {   Scanner sc=new Scanner(System.in);   String line=sc.nextLine();   String[] str=line.split(" ");   int n=str.length;   int[] array=new int[n];   for(int i=0;i<n;i++){    array[i]=Integer.parseInt(str[i]);   }   mySort(array);       }  private static void mySort(int[] array) {   LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();      int len=array.length;      for(int i=0;i<len;i++){    if(map.get(array[i])==null){     map.put(array[i], 1);    }else{     int count=map.get(array[i]);     count++;     map.put(array[i], count);    }   }        Set<Integer> key=map.keySet();   int n=key.size();   int[] value=new int[n];   int j=0;   for(int k:key){    value[j]=map.get(k);    j++;   }      Arrays.sort(value);      for(int i=n-1;i>=0;i--){    for(int k:key){     if(value[i]==map.get(k)){      for(int z=0;z<value[i];z++){       System.out.print(k);       System.out.print(" ");      }      map.put(k, 0);     }    }   }     } }

import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Scanner; public class TestZTE { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String s = sc.nextLine(); sort(s); } } private static void sort(String s) { String[] str = s.split(" "); // System.out.println(str.length); Map<String, Integer> map = new LinkedHashMap<String, Integer>(); List<Entry<String, Integer>> list = new ArrayList<>(); for (int i = 0; i < str.length; i++) { if (!map.containsKey(str[i])) { map.put(str[i], 1); } else { map.put(str[i], map.get(str[i]) + 1); } } for (Entry<String, Integer> entry : map.entrySet()) { list.add(entry); } Collections.sort(list, new Comparator<Entry<String, Integer>>() { @Override public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) { // TODO Auto-generated method stub return o2.getValue() - o1.getValue(); } }); StringBuffer sb = new StringBuffer(); for (Entry<String, Integer> list1 : list) { for (int i = 0; i < list1.getValue(); i++) { sb.append(list1.getKey()).append(" "); } } System.out.println(sb.toString().trim()); } }

用桶排序吧。简洁多了

思路比较繁琐，没仔细思考 仅仅实现了功能 #include <iostream> #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; bool cmp(pair<int, int> a, pair<int, int> b) {     return a.second > b.second; } int main() {     vector<int> v {1,1,1,1,3,3,3,4,5,2,6,6,6,6,6};     map<int, int> m;     for(int i = 0; i < v.size(); ++i)     {         if(m.find(v[i]) == m.end())         {             m.insert(make_pair(v[i], 1));         }         else         {             ++m[v[i]];         }     }     vector<pair<int, int>> res;     set<int> s;     for(int i = 0; i < v.size(); ++i)     {         if(s.find(v[i]) == s.end())         {             res.push_back(make_pair(v[i], m[v[i]]));             s.insert(v[i]);         }     }     stable_sort(res.begin(), res.end(), cmp);     for(int i = 0; i < res.size(); ++i)     {         for(int j = 0; j < res[i].second; ++j)         {             if(i == res.size() - 1 && j == res[i].second - 1)             {                 cout << res[i].first << endl;             }             else             {                 cout << res[i].first << " ";             }         }     } }

int main() { int A[]={1 ,1, 1, 1, 3, 3, 3, 4, 5, 2, 6, 6, 6, 6, 6 }; int len =sizeof(A)/sizeof(int); int ha[100]={0}; for(int i=0;i<len;i++) { ha[A[i]]++; } int i=0,j=0; int a[100][2]; for(int i=0;i<100;i++) { if(ha[i]!=0) { a[j][0]=i; a[j++][1]=ha[i]; } } int lena=j; for(int i=0;i<lena-1;i++)//冒泡排序 { for(int j=0;j<lena-1-i;j++) { if(a[j][1]<a[j+1][1])// { int t=a[j][1]; int d=a[j][0]; a[j][1]=a[j+1][1]; a[j][0]=a[j+1][0]; a[j+1][1]=t; a[j+1][0]=d; } if(a[j][1]==a[j+1][1])//若相等 { int d1=a[j][0]; int d2=a[j+1][0]; int k; for(k=0;k<len&&(A[k]!=d1)&&(A[k]!=d2);k++) { int aaa=k; } int d=A[k]; if (d2==d) { int t=a[j][1]; int dd=a[j][0]; a[j][1]=a[j+1][1]; a[j][0]=a[j+1][0]; a[j+1][1]=t; a[j+1][0]=dd; } } } } for (int i=0;i<lena;i++) { int num=a[i][1]; for(int j=0;j<num;j++) { cout<<a[i][0]<<' '; } } }

//用的linkedhashmap import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Scanner; public class Main { public static void sort(int[] num){ LinkedHashMap<Integer, Integer> map=new LinkedHashMap<>(); for (int i = 0; i < num.length; i++) { if (map.containsKey(num[i])) { map.put(num[i], map.get(num[i])+1); } else { map.put(num[i], 1); } } List<Map.Entry<Integer, Integer>> list=new ArrayList<>(map.entrySet()); Collections.sort(list,new Comparator<Map.Entry<Integer, Integer>>() { public int compare(Entry<Integer, Integer>o1,Entry<Integer, Integer>o2){ return o2.getValue().compareTo(o1.getValue()); } }); List<Integer> list1=new ArrayList<>(); List<Integer> list2=new ArrayList<>(); for(Entry<Integer, Integer> mapp:list){ list1.add(mapp.getKey()); list2.add(mapp.getValue()); } int[] newnum=new int[num.length]; int j=0; int index=0; for (int i = 0; i < list2.size(); i++) { while(index<list2.get(i)){ newnum[j]=list1.get(i); j++; index++; } index=0; } for (int i = 0; i < newnum.length; i++) { System.out.println(newnum[i]); } } public static void main(String[] args) { int[] num={1,1,1,2,3,3,4}; sort(num); } }

可以用stable_sort()吗，自己定义个compare，针对map里面键值对的第二项（就是出现次数）来排序。

public static void main(String[] args) { // TODO Auto-generated method stub      int []arr={1, 1, 1, 1, 3, 3, 3, 4, 5, 2 ,6, 6, 6, 6, 6};      int[]hasArray=new int[arr.length+1];      int maxLength=0;      for(int i=0;i<arr.length;i++)      {     hasArray[arr[i]%hasArray.length]+=1;     maxLength=hasArray[arr[i]%hasArray.length]>maxLength?hasArray[arr[i]%hasArray.length]:maxLength;      }      while(maxLength>=1)      {     for(int i=0;i<arr.length;i++)     {     if(hasArray[arr[i]%hasArray.length]==maxLength)     {     System.out.print(arr[i]%hasArray.length+" ");     }         }     maxLength--;      } }

#include<iostream> #include<vector> #include<string> #include <algorithm> using namespace std; bool cmp_by_value(pair<int, int> lhs, pair<int, int>rhs) { return lhs.second > rhs.second; } int main() { vector<int> vec; string str; getline(cin,str); while(true) { if(str.find_first_of(' ')!=string::npos) { string strTmp=str.substr(0, str.find_first_of(' ')); vec.push_back(atoi(strTmp.c_str())); str = str.substr(str.find_first_of(' ')+1, str.size()); } else { vec.push_back(atoi(str.c_str())); break; } } vector<int> v=vec; vector<int>::iterator iter = v.begin(); while(iter != v.end()){ if(iter != find(v.begin(),iter,*iter)){ iter = v.erase(iter); continue; } iter++; } vector<pair<int,int> >new_vec; for (int i=0;i<v.size();i++) { new_vec.push_back(make_pair<int,int>(v[i],count(vec.begin(),vec.end(),v[i]))); } sort(new_vec.begin(), new_vec.end(), cmp_by_value); for (int i = 0; i != new_vec.size(); ++i) { int count=new_vec[i].second; for (int j=0;j<count;j++) { cout<<new_vec[i].first<<" "; } } cout<<endl; return 0; }

原数组再遍历一遍不就行了么

代码过于繁琐，不是很给力。。。

每个数再增加一个"第一次出现的位置"这个属性，这样排序的时候，先根据每个数出现的次数排序，相同时再根据每个数第一次出现的位置排序。