某个正整数的数根定义为其所有数字之和

Question

我试图在一个在线挑战网站上解决这个挑战，但我有点卡住了。这里有更多关于这个问题的信息：给你一个整数数组。以这样的方式对其进行排序，如果 a 在 b 之前，则 a 的数根小于或等于 b 的数根。如果两个数字具有相同的数根，则较小的（通常意义上的）应该排在第一位。例如，4 和 13 具有相同的数字根，但是 4 < 13 因此 4 在任何 digitRoot 排序中都出现在 13 之前。这是我的输出：Input: a: [13, 20, 7, 4]Output: [20, 13, 4, 7]Expected Output: [20, 4, 13, 7]这是我的代码：int digitRoot(int b) {    int c, sum = 0;    while(b>0) {        c=b%10;        sum=sum+c;        b=b/10;    }    return sum;}int[] digitRootSort(int[] a) {    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();    int[] a1 = new int[a.length];    for (int i=0;i<a.length;i++) {        a1[i]=digitRoot(a[i]);        if (map.containsKey(a1[i])) {            ArrayList<Integer> temp = map.get(a1[i]);            temp.add(a[i]);            map.put(a1[i], temp);        }        else {             ArrayList<Integer> list = new ArrayList<Integer>();            list.add(a[i]);            map.put(a1[i], list);        }    }    Arrays.sort(a1);    for (int i=0;i<a.length;i++) {        ArrayList<Integer> temp = map.get(a1[i]);        for(int j=0;j<temp.size();j++) {            a[i]=temp.get(j);            if (j<temp.size()-1)                i++;        }    }    return a;}但是如果我改变 map.put(a1[i], temp); 到 map.put(a1[i], Collections.sort(temp));，我收到这个错误：file.java 在第 24 行： error: 'void' type not allowed here                map.put(a1[i], Collections.sort(list));

Answer 1

只需Collections.sort(temp);在最后一个 for 循环中包含这个，这是必要的，因为多个数字可以具有相同的 digitRoot 并且应该放在已排序的列表中。

for (int i=0;i<a.length;i++) {

        ArrayList<Integer> temp = map.get(a1[i]);

        Collections.sort(temp);

        for(int j=0;j<temp.size();j++) {

            a[i]=temp.get(j);

            if (j<temp.size()-1)

                i++;

        }

    }

Input: a: [13, 20, 7, 4]

Output: [20, 4, 13, 7]

编辑：关于错误

因为在put(a1[i], Collections.sort(list))put 方法中是期望的put(int, List)，但是你给了它put(int, void)，因为返回类型Collections.sort()是void，你只需要先对列表进行排序然后再通过

Answer 2

您似乎正在尝试插入集合的排序值。Collections.sort(List)，无论好坏，就地对该列表进行排序并且不返回任何内容。先对列表进行排序，然后将其插入到地图中。

Answer 3

放入地图时不需要对数组进行排序。相反，您可以在最后一个循环中检索时对其进行排序：

    Arrays.sort(a1);

    for (int i=0;i<a.length;i++) {

        ArrayList<Integer> temp = map.get(a1[i]);

        Collections.sort(temp);

        for(int j=0;j<temp.size();j++) {

            a[i]=temp.get(j);

            if (j<temp.size()-1)

                i++;

        }

    }

如果您需要在放入地图时进行排序，您应该使用 SortedSet 因为它会自动保持元素排序：

int[] digitRootSort(int[] a) {

    HashMap<Integer, TreeSet<Integer>> map = new HashMap<Integer, TreeSet<Integer>>();

    int[] a1 = new int[a.length];

    for (int i = 0; i < a.length; i++) {

        a1[i] = digitRoot(a[i]);

        if (map.containsKey(a1[i])) {

            TreeSet<Integer> set = map.get(a1[i]);

            set.add(a[i]);

            map.put(a1[i], set);

        } else {

            TreeSet<Integer> set = new TreeSet<Integer>();

            set.add(a[i]);

            map.put(a1[i], set);

        }

    }

    Arrays.sort(a1);

    for (int i = 0; i < a.length;) {

        TreeSet<Integer> set = map.get(a1[i]);

        for (int j : set) {

            a[i] = j;

            i++;

        }

    }

    return a;

}

但是，通过使用适当的比较器，还有一种更简单的方法来处理排序集：

int[] digitRootSort(int[] a) {

    SortedSet<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {

        @Override

        public int compare(Integer a, Integer b) {

            int result = Integer.compare(digitRoot(a), digitRoot(b));

            result = result == 0 ? Integer.compare(a, b) : result;

            return result;

        }

    });

    for (int i : a) {

        set.add(i);

    }

    int i = 0;

    for (int j : set) {

        a[i++] = j;

    }

    return a;

}