排列员工工资顺序（C++map解法）
题目描述：
某公司中有N名员工。给定所有员工工资的清单，财务人员要按照特定的顺序排列员工的工资。他按照工资的频次降序排列。即给定清单中所有频次较高的工资将在频次较低的工资之前出现。如果相同数量的员工都有相同的工资，则将按照给定清单中该工资第一次出现的顺序排列。
写一个算法来帮助财务人员排列员工工资的顺序。
输入：
该函数/方法的输入包括两个参数------
num，一个整数，表示员工的人数
salaries，一个正整数列表，表示N名员工的工资
输出：
返回一个正整数列表，该列表按照员工工资的频次排序。
约束条件：
1<num<100000
1<salaries<1000000000
0<i<num
示例：
输入：num=19
salaries=[10000,20000,40000,30000,30000,30000,40000,20000,50000,50000,50000,50000,60000,60000,60000,70000,80000,90000,100000]
输出：
[50000,50000,50000,50000,30000,30000,30000,60000,60000,60000,20000,20000,40000,40000,10000,70000,80000,90000,100000]
解题思路：使用map保存工资出现的频次，若没有该条工资，加入；若有该条工资，频次+1。然后遍历map找频次的最大值，根据频次吧key值加入vector中，然后删除该条记录，直到map为空。返回vector即可。
#include <map> #include <vector> using namespace std; int main() { int num = 19; int *salaries = new int[19]{ 100,200,400,300,300,300,400,200,500,500,500,500,600,600,600,700,800,900,1000 }; vector<int> result = salaryFrequeny(19, salaries); system("pause"); return 0; } vector<int> salaryFrequeny(int num, int *salaries) { map<int, int> safMap; map<int, int>::iterator iter; for (int i = 0; i < num; i++) { iter = safMap.find(salaries[i]); if (iter == safMap.end()) { safMap.insert(pair<int, int>(salaries[i], 1));//没找到key值，向map加入。 } else { iter->second += 1;//找到key值，对应的value+1 } } vector<int> result; int max = 0; int index = 0; while (safMap.size()) { for (iter = safMap.begin(); iter != safMap.end(); iter++)//找当前频次最高的记录 { if (iter->second > max) { max = iter->second; index = iter->first; } } while (max--) { result.push_back(index);//将频次最高的key值按频次压入vector } safMap.erase(index);//擦除当前频次最高的记录 } return result; }
【转载自】
627在线笔试题：排列员工工资顺序（C++map解法） - 懂代码的暖男 - CSDN博客
题目：排列员工工资顺序（Java和C++）（中兴在线笔试题） - 会笑的小猪的博客 - CSDN博客
题目描述： 某公司中有N名员工。给定所有员工工资的清单，财务人员要按照特定的顺序排列员工的工资。他按照工资的频次降序排列。即给定清单中所有频次较高的工资将在频次较低的工资之前出现。如果相同数量的员工都有相同的工资，则将按照给定清单中该工资第一次出现的顺序排列。 写一个算法来帮助财务人员排列员工工资的顺序。 �0�2 输入： 该函数/方法的输入包括两个参数------ num，一个整数，表示员工的人数 salaries，一个正整数列表，表示N名员工的工资 输出： 返回一个正整数列表，该列表按照员工工资的频次排序。 约束条件： 1<num<100000 1<salaries<1000000000 0<i<num �0�2 示例： 输入： num=19 salaries=[10000,20000,40000,30000,30000,30000,40000,20000,50000, 50000,50000,50000,60000,60000,60000,70000,80000,90000,100000] 输出： [50000,50000,50000,50000,30000,30000,30000,60000,60000, 60000,20000,20000,40000,40000,10000,70000,80000,90000,100000] �0�2 �0�2 分析：本题要求把根据数据出现的频数从高到低排序，所以基本的思路是算出每个数的频次，然后直接从高到低排序。 �0�2 �0�2 �0�2 �0�2 �0�2 �0�2可是这样会出现一个问题，频次相同的数据没法排序。比如 20 40�0�220�0�240 50 这组数据分别得到频次 2 2 2 2 1，本身就是一个降序排序，所以最后结果还是20 40 20 40 50 �0�2 �0�2 �0�2 �0�2 �0�2 �0�2那怎么办呢？我们可以上面那种数据中间那个20为例，即20 40 20 40 50。首先我们来判断20的前半部分是否存在20，如果存在20的话则插入到该20的后面即可，即变为20 20 40 40 50。 �0�2 �0�2 �0�2 �0�2 �0�2 �0�2所有排序过程均使用插入排序。插入排序的详细原理读者可以自行百度，插入排序从后往前移动，移动过程中不会改变原有已经排列好的数字的顺序。 �0�2 思路：1.计算每个数的频数。 �0�2 �0�2 �0�2 �0�2 �0�2 �0�22.根据频数的大小，对数据从高到低排序。排序的方法使用插入排序。 �0�2 �0�2 �0�2 �0�2 �0�2 3. 对第2部排好序的结果再排序。这次从前向后遍历，判断该数的前半部分是否存在该数，存在的话就插入到最近和它相同数的后面。 Java实现： 在线运行代码 public class salaryArrangement { public static void main(String[] args) { int num = 19; int slalay[] = { 10000, 20000, 40000, 30000, 30000, 30000, 40000, 20000, 50000, 50000, 50000, 50000, 60000, 60000, 60000, 70000, 80000, 90000, 100000 };// 测试数据 slalay = b(num, slalay); // 保存结果 int i; System.out.println("输出结果为："); for (i = 0; i < num; i++)// 输出结果 { System.out.print(" "); System.out.print(slalay[i]); } } public static int[] b(int num, int slalay[]) { int i, j, k; int temp_frequency; int temp_slalay; int frequency[] = new int[num]; // 频次 for (i = 0; i < num; i++) // 给频次赋初值 { frequency[i] = 0; } for (i = 0; i < num; i++) // 对已排序的数据统计频次 { for (j = 0; j < num; j++) { if (slalay[i] == slalay[j]) { frequency[i]++; } } } for (i = 1; i < num; i++) // 对频次进行插入排序，同时根据频数交换的顺序排列原数据 { temp_frequency = frequency[i]; temp_slalay = slalay[i]; j = i - 1; while (j >= 0 && temp_frequency > frequency[j]) //频次递减排序 { frequency[j + 1] = frequency[j]; slalay[j + 1] = slalay[j]; // 变换原数据 j--; } frequency[j + 1] = temp_frequency; slalay[j + 1] = temp_slalay; } for (i = 1; i < num; i++) // 再进行一次插入排序 { temp_slalay = slalay[i]; j = i - 1; k = i - 1; while (k >= 0) { if (temp_slalay == slalay[k]) // 判断前半部分子序列是否存在当前当前数据 { while (j >= 0 && temp_slalay != slalay[j]) // 插入到相同的数的后面 { slalay[j + 1] = slalay[j]; j--; } slalay[j + 1] = temp_slalay; break; // 退出循环判断下个数 } k--; } } return slalay; } } C++实现： 在线运行代码 #include <stdio.h> int* b(int num, int* slalay) { int i, j, k; int temp_frequency; int temp_slalay; int frequency[num]; // 频次 for (i = 0; i < num; i++) // 给频次赋初值 { frequency[i] = 0; } for (i = 0; i < num; i++) // 对已排序的数据统计频次 { for (j = 0; j < num; j++) { if (slalay[i] == slalay[j]) { frequency[i]++; } } } for (i = 1; i < num; i++) // 对频次进行插入排序，同时根据频数交换的顺序排列原数据 { temp_frequency = frequency[i]; temp_slalay = slalay[i]; j = i - 1; while (j >= 0 && temp_frequency > frequency[j]) //频次递减排序 { frequency[j + 1] = frequency[j]; slalay[j + 1] = slalay[j]; // 变换原数据 j--; } frequency[j + 1] = temp_frequency; slalay[j + 1] = temp_slalay; } for (i = 1; i < num; i++) // 再进行一次插入排序 { temp_slalay = slalay[i]; j = i - 1; k = i - 1; while (k >= 0) { if (temp_slalay == slalay[k]) // 判断前半部分子序列是否存在当前当前数据 { while (j >= 0 && temp_slalay != slalay[j]) // 插入到相同的数的后面 { slalay[j + 1] = slalay[j]; j--; } slalay[j + 1] = temp_slalay; break; // 退出循环判断下个数 } k--; } } return slalay; } int main() { int num = 19; int slalay[19] = { 10000, 20000, 40000, 30000, 30000, 30000, 40000, 20000, 50000, 50000, 50000, 50000, 60000,60000, 60000, 70000, 80000, 90000, 100000 };// 测试数据 int *slalayResult; slalayResult = b(num, slalay); // 保存结果 int i; printf("输出结果为："); for (i = 0; i < num; i++)// 输出结果 { printf("%d ",slalayResult[i]); } }