按因数个数降序排列整数数组的优化实现问询（Zoho笔试题）

要求将给定整数按因数个数降序排列：

• 输入示例：4,2,8,16,5
• 输出示例：16,8,4,5,2 或 16,8,4,2,5（因数个数相同时，顺序不做要求）

你当前通过创建因数计数数组、同步排序计数数组与原数组的方式完成需求，Java代码如下：

import java.util.Scanner;

public class DecreasingIntAccToFactors {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        // Static Way of Array Creation
        // int[] a = { 3, 4, 7, 8, 16, 33 };

        // Dynamic Way of Array Creation
        System.out.print("Enter the Size of an Array :- ");
        int n = sc.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < a.length; i++) {
            System.out.print("Enter the Elements of an Array [ " + i + " ] :- ");
            a[i] = sc.nextInt();
        }

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

        // Creating a Count Array to Store the No. of Factors that a Number has
        // According to their Array order
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = a[i] - 1; j > 0; j--) {
                if (a[i] % j == 0) {
                    count++;
                }
            }
            f_count[i] = count;
        }

        // Printing the Given Array with the Help of Method
        System.out.println("Given Array : - ");
        printingArray(a);
        System.out.println();
        System.out.println("The Factors of the Given Array :-");
        printingArray(f_count);

        // Sorting the Count Array and Swapping the Given Array
        for (int i = 0; i < f_count.length - 1; i++) {
            for (int j = 0; j < f_count.length - 1; j++) {
                if (f_count[j] < f_count[j + 1]) {
                    // Swapping elements of the Count Array
                    int temp_c = f_count[j];
                    f_count[j] = f_count[j + 1];
                    f_count[j + 1] = temp_c;
                    // Swapping the Elements according to Count Array
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }

            }
        }

        // Printing the Resultant Array with the help of Method
        System.out.println("\n\n");
        System.out.println("Resultant Array : - ");
        printingArray(a);
        System.out.println();
        System.out.println("The Factors of the Resultant Array :-");
        printingArray(f_count);

    }

    // Printing the Array
    public static void printingArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}

当然有更简洁、逻辑更优的实现，核心优化点如下：

• 替换手动排序为Java内置排序：放弃自己实现的冒泡排序，改用Collections.sort()结合自定义比较器，代码更简洁，且内置TimSort的时间复杂度为O(n log n)，远优于冒泡排序的O(n²)。
• 优化因数计数算法：将原来从n-1遍历到1的低效逻辑，改为遍历到√n——因数是成对出现的，每找到一个因数就计数+2，最后处理平方数的特殊情况，大幅减少遍历次数。
• 消除同步数组维护：直接对整数列表排序，比较时实时计算因数个数，无需单独维护计数数组，避免同步错误。

优化后的完整代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class SortByFactorCount {
    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        // 输入数组
        System.out.print("Enter the Size of an Array :- ");
        int n = sc.nextInt();
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            System.out.print("Enter the Elements of an Array [ " + i + " ] :- ");
            numbers.add(sc.nextInt());
        }

        // 打印原数组
        System.out.println("Given Array : - ");
        printList(numbers);

        // 按因数个数降序排序
        Collections.sort(numbers, (num1, num2) -> {
            int count1 = countFactors(num1);
            int count2 = countFactors(num2);
            // 降序排列，因数个数相同时顺序随意
            return Integer.compare(count2, count1);
        });

        // 打印结果
        System.out.println("\nResultant Array : - ");
        printList(numbers);
    }

    // 优化的因数计数方法
    private static int countFactors(int num) {
        if (num == 1) return 1;
        int count = 0;
        int sqrt = (int) Math.sqrt(num);
        for (int i = 1; i <= sqrt; i++) {
            if (num % i == 0) {
                // 处理平方数的情况
                if (i == num / i) {
                    count++;
                } else {
                    count += 2;
                }
            }
        }
        return count;
    }

    // 打印列表
    private static void printList(List<Integer> list) {
        for (int num : list) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

额外扩展 #

如果需要在因数个数相同时按数值排序，只需修改比较器逻辑即可：

Collections.sort(numbers, (num1, num2) -> {
    int count1 = countFactors(num1);
    int count2 = countFactors(num2);
    if (count1 != count2) {
        return Integer.compare(count2, count1);
    } else {
        // 因数个数相同时按数值升序排列
        return Integer.compare(num1, num2);
    }
});

内容的提问来源于stack exchange，提问作者Suriya Jaisankar