找出数组中每个元素相对其他元素的大小 – moqiguzhu
题目可能表述不是十分清楚，举个例子。
假设一个数组，元素分别是3 9 2 1 8 3 2，需要输出3 5 2 1 4 3 2，输出中的3表示元素3在数组所有的元素中是排在第三位的，比1 2 大，5表示9在数组所有的元素中是排在第五位的，也就是最大的。
思路：首先想到的是可不可以通过各种各样的排序方法解决这个问题，我们知道在排序的时候，元素的位置信息是不被保留的，但是这里的输出要求按元素在数组中原始的排列顺序输出。我们可以在排序算法的基础上稍作修改就okay了。下面的实现借鉴了冒泡排序的思想。
import java.io.File;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Scanner; /*repeat exception class*/
class RepeatException extends Exception{
RepeatException()
{
super.printStackTrace();
System.out.println(str);
}
/**
*
* @param al — ArrayList store elements in original double array
* @param positionInfo — ArrayList store position information, for example, al = {1,2,1}
* then, positionInfo = {0,1,0}, the second 0 means the relative order of this elements is
* store in the first position of result (return by computeNumber)
* @return
*/
public static ArrayList<Double> deleteRepeat(ArrayList<Double> al, ArrayList<Integer> positionInfo){
//flag record position information
int flag = 0;
{
if(temp.contains(al.get(i)))
{
positionInfo.add(temp.indexOf(al.get(i)));
}
else
{
positionInfo.add(flag);
flag++;
temp.add(al.get(i));
}
}
return temp;
}
*
* @param noRepeatArray ArrayList after delete repeat elements
* @return return the relative order of every element in noRepeatArray
* @throws Exception throw exception if repeat elements are found in noRepeatArray
*/
public static int[] computeNumber(ArrayList<Double> noRepeatArray) throws Exception{
for(int i = 0; i < result.length; i++)
{
result[i] = 1;
}
{
for(int j = i+1; j < noRepeatArray.size(); j++)
{
if(noRepeatArray.get(i) < noRepeatArray.get(j))
result[j]++;
if(noRepeatArray.get(i) > noRepeatArray.get(j))
result[i]++;
if(noRepeatArray.get(i) == noRepeatArray.get(j))
throw new RepeatException();
}
}
}
ArrayList<Double> al = new ArrayList<Double>();
ArrayList<Integer> positionInfo = new ArrayList<Integer>();
for(int i = 0; i < test.length; i++)
{
al.add(test[i]);
}
try
{
int[] result = computeNumber(al);
for(int i = 0; i < output.length; i++)
{
output[i] = result[positionInfo.get(i)];
System.out.print(output[i] + ” “);
}
{
e.printStackTrace();
}
}
outputResult(test);
}
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Scanner; /*repeat exception class*/
class RepeatException extends Exception{
private static final long serialVersionUID = 1L;
static String str = “elements can not repeat!!!”;
/*constructor*/
RepeatException()
{
super.printStackTrace();
System.out.println(str);
}
}
public class WhatIsMyNumber {/**
*
* @param al — ArrayList store elements in original double array
* @param positionInfo — ArrayList store position information, for example, al = {1,2,1}
* then, positionInfo = {0,1,0}, the second 0 means the relative order of this elements is
* store in the first position of result (return by computeNumber)
* @return
*/
public static ArrayList<Double> deleteRepeat(ArrayList<Double> al, ArrayList<Integer> positionInfo){
ArrayList
<Double> temp = new ArrayList<Double>();//flag record position information
int flag = 0;
for(int i = 0; i < al.size(); i++)
{
if(temp.contains(al.get(i)))
{
positionInfo.add(temp.indexOf(al.get(i)));
}
else
{
positionInfo.add(flag);
flag++;
temp.add(al.get(i));
}
}
return temp;
}
/**
*
* @param noRepeatArray ArrayList after delete repeat elements
* @return return the relative order of every element in noRepeatArray
* @throws Exception throw exception if repeat elements are found in noRepeatArray
*/
public static int[] computeNumber(ArrayList<Double> noRepeatArray) throws Exception{
int[] result = new int[noRepeatArray.size()];
for(int i = 0; i < result.length; i++)
{
result[i] = 1;
}
for(int i = 0; i < noRepeatArray.size(); i++)
{
for(int j = i+1; j < noRepeatArray.size(); j++)
{
if(noRepeatArray.get(i) < noRepeatArray.get(j))
result[j]++;
if(noRepeatArray.get(i) > noRepeatArray.get(j))
result[i]++;
if(noRepeatArray.get(i) == noRepeatArray.get(j))
throw new RepeatException();
}
}
return result;
}
public static void outputResult(double[] test){
double[] output = new double[test.length];
ArrayList<Double> al = new ArrayList<Double>();
ArrayList<Integer> positionInfo = new ArrayList<Integer>();
for(int i = 0; i < test.length; i++)
{
al.add(test[i]);
}
al
= deleteRepeat(al,positionInfo);try
{
int[] result = computeNumber(al);
for(int i = 0; i < output.length; i++)
{
output[i] = result[positionInfo.get(i)];
System.out.print(output[i] + ” “);
}
System.out.println();
}
{
e.printStackTrace();
}
}
public static void main(String[] args){
double[] test = new double[]{8,8,8,2.5,8,8,2.5,8,13,15,12,2.5,15,2.5,8,15};
outputResult(test);
}
下面来说说程序的主要思想。
给定一个数组，假设是{5,2,4,1}，输出数组初始化为{1,1,1,1}，然后5和2比较，5>2，输出数组变为{2,1,1,1}，5和4比较，5>4，输出数组变为{3,1,1,1}，5和1比较，5>1，输出数组变为{4,1,1,1}，这是一轮，下一轮，2分别与4和1比较，最后是4和1比较。最后输出数组是{4,2,3,1}。
如果数组中存在重复的元素，两个一样大小的元素得到的relative order可能是不一致的，所以在实现的时候书写了deleteRepeat这样一个函数，并且用positionInfo来保存位置信息。
本文链接：找出数组中每个元素相对其他元素的大小，转载请注明。
