algorithm - 【面试】求正整数排列的任意排列可以组成的最大值

Question

给定一个正整数数组，找出排列的任意排列可以形成的最大值。我想知道是否有更好的数据结构可以为问题提供更优雅的解决方案。

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;
    }
}

Answer 1

恕我直言，一般情况(将任意非负整数粘合在一起，不一定是数字)非常有趣，例如

 [709, 8, 70, 71, 5, 7] -> 8771709705
 [31, 34, 30, 3]        -> 3433130
 [334, 323, 30, 31, 3]  -> 33433233130

思路和H2CO3提到的一样:数组排序，但实现 (C#) 不同

private static int Compare(int x, int y) {
  if (x == y)
    return 0;

  // Not that good solution (to compare chars), but easy to implement
  String Stx = x.ToString(CultureInfo.InvariantCulture);
  String Sty = y.ToString(CultureInfo.InvariantCulture);

  int n = Stx.Length < Sty.Length ? Stx.Length : Sty.Length;

  // Standard lexicographic comparison: 9 > 80, 293 > 2896, 9873 > 986 etc.
  for (int i = 0; i < n; ++i)
    if (Stx[i] > Sty[i])
      return 1;
    else if (Stx[i] < Sty[i])
      return -1;

  // Special case: ab <>= a? 
  // 70 < 7; 78 > 7 etc
  if (Stx.Length > Sty.Length) {
    for (int i = n; i < Stx.Length; ++i)
      if (Stx[i - 1] > Stx[i])
        return -1;
      else if (Stx[i - 1] < Stx[i])
        return 1;
  }
  else {
    for (int i = n; i < Sty.Length; ++i)
      if (Sty[i - 1] > Sty[i])
        return 1;
      else if (Sty[i - 1] < Sty[i])
        return -1;
  }

  return 0;
}

然后

int[] data = new int[] { 709, 8, 70, 71, 5, 7 };
Array.Sort(data, Compare);

StringBuilder Sb = new StringBuilder();

for (int i = data.Length - 1; i >= 0; --i)
  Sb.Append(data[i]);

// 8771709705
String result = Sb.ToString();