给定一个正整数数组,找到可以由排列的任何排列形成的最大值。我想知道是否有更好的数据结构可以为问题提供更优雅的解决方案。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class FindMaximumNumbersFromPermutation {
static class DS implements Comparable<DS> {
int intAtI;
Integer[] actualInt;
public DS(int intAtI, Integer[] actualInt) {
super();
this.intAtI = intAtI;
this.actualInt = actualInt;
}
@Override
public int compareTo(DS o) {
if(intAtI < o.intAtI)
return 1;
else if(intAtI == o.intAtI)
return 0;
else return -1;
}
@Override
public String toString() {
String s="";
for(int i=0;i<actualInt.length;i++)
s= s+actualInt[i];
return s;
}
}
public static void main(String[] args)
{
int[] arr = {21,9,23};
List<Integer[]> list = new ArrayList<Integer[]>();
int maxLength= 0;
for(int i=0;i<arr.length;i++)
{
Integer[] digitsArray = getDigitsArray(arr[i]);
if(digitsArray.length > maxLength)
maxLength = digitsArray.length;
list.add(digitsArray);
}
List<Integer[]> output = new ArrayList<Integer[]>();
for(int currentLength=0;currentLength<=maxLength;currentLength++)
doWork(list, output, currentLength);
for(int i=0;i<output.size();i++)
{
Integer[] temp = output.get(i);
for(int j=0;j<temp.length;j++)
{
System.out.print(temp[j]);
}
}
}
private static void doWork(List<Integer[]> list, List<Integer[]> output,
int currentLength) {
List<DS> dsList = new ArrayList<DS>();
for(int i=0;i<list.size();i++)
{
Integer[] temp = list.get(i);
if(temp.length>currentLength)
{
dsList.add(new DS(temp[currentLength],temp));
}
}
Collections.sort(dsList);
Map<Integer,List<Integer[]>> map = new TreeMap<Integer,List<Integer[]>>();
for(int i=0;i<dsList.size();i++)
{
DS ds = dsList.get(i);
if(!map.containsKey(ds.intAtI))
{
List<Integer[]> l = new ArrayList<Integer[]>();
l.add(ds.actualInt);
map.put(ds.intAtI, l);
}
else
{
List<Integer[]> l = map.get(ds.intAtI);
l.add(ds.actualInt);
map.put(ds.intAtI, l);
}
}
ArrayList<Integer> keys = new ArrayList<Integer>(map.keySet());
for(int i=keys.size()-1;i>=0;i--)
{
Integer key = keys.get(i);
List<Integer[]> l = map.get(key);
if(l.size() ==1)
output.add(l.get(0));
}
}
static Integer[] getDigitsArray(int integer)
{
String s = integer+"";
Integer[] ret = new Integer[s.length()];
for(int i=0;i<s.length();i++)
{
ret[i] = Integer.parseInt(s.charAt(i)+"");
}
return ret;
}
}