输出数组中数目字排名(不允许并列排名)
输出数组中数字排名(不允许并列排名) 算法一(有缺陷的算法)：将当前元素大于数组中元素的个数作为其排名。 算例如下： 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的排名。 算法二(性能不够好的算法)：针对算法一进行改进，对算法一中形成的序列进行额外的去重操作。 算例如下： 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)。 算法三(相对合理的算法)：从当前排名中去除其前的元素个数作为其真正的排名。 算例如下： 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。/**
* 算法一
* 思路:将每个数组中元素与整个数组中的所有元素(包括自身)比较,
* 累计该元素大于等于整个数组中元素个数
* */
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;
}
}
/**
* 算法二
* 思路:将每个数组中元素与整个数组中的所有元素(包括自身)比较,
* 累计该元素大于等于整个数组中元素个数
*
* 扫描上述产生的序列,特别处理重复的元素:
* 查看当前元素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;
}
/**
* 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] + " ");
}
}
}