输出数组中数字排名(不允许并列排名)
?
?
?
输出数组中数字排名(不允许并列排名)
?
?
?
?
算法一(有缺陷的算法)：将当前元素大于数组中元素的个数作为其排名。
?
/** * 算法一 * 思路:将每个数组中元素与整个数组中的所有元素(包括自身)比较, * 累计该元素大于等于整个数组中元素个数 * */private static void codeToLocation(double[] code, int[] location){for(int i=0; i<code.length; i++){int count = 0;for(int j=0; j<code.length; j++){if(code[i] >= code[j]){count++;}}location[i] = count;}}?算例如下：
double[] code = {2.9, 8.5, 5.7, 8.0, 5.4, 3.2, 8.9, 2.8, 5.8};
displayLocation(codeToLocation(code));
?
---------- 运行Java ----------
2 8 5 7 4 3 9 1 6?
输出完成 (耗时 0 秒) - 正常终止
?
?
该算法缺陷：不能处理包含相同元素的数组。例：
double[] code = {2.9, 8.5, 5.7, 8.0, 5.7, 3.2, 8.9, 2.8, 5.7};
displayLocation(codeToLocation(code));//打印数组中元素
?
---------- 运行Java ----------
2 8 6 7 6 3 9 1 6?
输出完成 (耗时 0 秒) - 正常终止
?
从输出结果看出，该输出序列包含3个6，多了2个6，少了4和5的排名。
?
?
?
?
算法二(性能不够好的算法)：针对算法一进行改进，对算法一中形成的序列进行额外的去重操作。
?
/** * 算法二 * 思路:将每个数组中元素与整个数组中的所有元素(包括自身)比较, * 累计该元素大于等于整个数组中元素个数 * * 扫描上述产生的序列,特别处理重复的元素: * 查看当前元素location[i]前的所有元素location[0,i-1]中是否有与当前元素location[i]相同的元素存在 * 若有,则当前的元素location[i]排名减1;并继续迭代,若有与经减1操作后相等的元素,则当前元素排名再减1 * * 如:序列2 8 6 7 6 3 9 1 6 * 第二个6变成5后序列变为2 8 6 7 5 3 9 1 6 * 第三个6先要与第一个6比较,减1,序列变为2 8 6 7 5 3 9 1 5 * 还需要继续迭代,当扫描到5时,因为最后一个5减1,序列变为2 8 6 7 5 3 9 1 4 * */private static int[] codeToLocation(double[] code){int location[] = new int[code.length];for(int i=0; i<code.length; i++){int count = 0;for(int j=0; j<code.length; j++){if(code[i] >= code[j]){count++;}}location[i] = count;/** * 处理重复的元素 * */for(int j=0; j<i; j++){if(location[j] == location[i])location[i]--;}}return location;}?算例如下：
double[] code = {2.9, 8.5, 5.7, 8.0, 5.7, 3.2, 8.9, 2.8, 5.7};
displayLocation(codeToLocation(code));//打印数组中元素
?
---------- 运行Java ----------
2 8 6 7 5 3 9 1 4?
输出完成 (耗时 0 秒) - 正常终止
?
?
性能不够好的算法：算法的时间复杂度是2倍的O(n^2)。
?
?
?
算法三(相对合理的算法)：从当前排名中去除其前的元素个数作为其真正的排名。
?
/** * Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC) * All rights reserved. * Author: Jarg Yee <yeshaoting@gmail.com> * http://jarg.iteye.com/ *//* * 输出数组中数字排名(不允许并列排名) */public class Test{public static void main(String[] args){double[] code = {2.9, 8.5, 5.7, 8.0, 5.7, 3.2, 8.9, 2.8, 5.7};displayLocation(codeToLocation(code));}/** * 算法三 * 思路:将每个数组中元素与整个数组中的所有元素(包括自身)比较, * 累计该元素大于等于整个数组中元素个数count * * 在累计的同时,记录当前位置前所有元素中与当前位置相同的元素个数pre * count-pre作为当前元素的排名. * */private static int[] codeToLocation(double[] code){int location[] = new int[code.length];for(int i=0; i<code.length; i++){int pre = 0;//记录当前位置前与当前元素相同的元素个数int count = 0;//所有元素(包括自身)大于等于当前元素的个数for(int j=0; j<code.length; j++){if(code[i] >= code[j]){/** * 记录当前位置前与当前元素相同的元素个数 * */if(j<i && code[i] == code[j])pre++;count++;}}count = count - pre;//将总排名减去前面相同元素个数当作当前元素的排名location[i] = count;}return location;}private static void displayLocation(int[] location){for(int i=0; i<location.length; i++){System.out.print(location[i] + " ");}}}??
算例如下：
double[] code = {2.9, 8.5, 5.7, 8.0, 5.7, 3.2, 8.9, 2.8, 5.7};
displayLocation(codeToLocation(code));//打印数组中元素
?
---------- 运行Java ----------
2 8 6 7 5 3 9 1 4?
输出完成 (耗时 0 秒) - 正常终止
?
?
相对合理的算法：能够处理包含重复元素的数组排名问题，时间复杂度为O(n^2)，相对于算法一和算法二来说，只多用了一个变量存储空间pre。