输出数组中数字排名(不允许并列排名)

 

 

 

输出数组中数字排名(不允许并列排名)

 

 

 

 

算法一(有缺陷的算法)：将当前元素大于数组中元素的个数作为其排名。

 

/**
 * 算法一
 * 思路:将每个数组中元素与整个数组中的所有元素(包括自身)比较,
 * 累计该元素大于等于整个数组中元素个数
 * */
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 <[e-mail]>
 * 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。