按字典顺序对int数组进行排序 [英] Sorting an array of int in lexicographic order

问题描述

我遇到了一个问题：

WAP按数字排序小于给定N的素数。如果N是40，
输出应该是11,13,17,19,2,23,29,3,31,37,39,5,7。
注意：限制内存使用。

WAP to sort prime numbers smaller than given N by digits. If N is 40, the output should be 11, 13, 17, 19, 2, 23, 29, 3, 31, 37, 39, 5, 7. Note: Limit memory use.

获取主号码非常简单。但我无法找出一种有效的整数数组排序方法。

Getting primary number was the easy. But I could not figure out an efficient way of lexicographic sorting of array of integer.

public static void getPrimeNumbers(int limit) {
        for (int i=2; i<=limit; i++) {
            if(isPrime(i)) {
                System.out.println(i);
            }
        }
    }

    public static boolean isPrime(int number) {
        for(int j=2; j<number; j++) {
            if(number%j==0) {
                return false;
            }
        }
            return true;
    }

    public static void lexographicSorting() {
        int[] input = {2,3,5,7,11,13,17,19};
        int[] output = {};
        for (int i=0; i<input.length; i++) {
            for(int j=0; j<input.length; j++) {
                ////Stuck at this part.
            }
        }
    }

推荐答案

考虑到问题的限制，解决此问题的更有效方法是根本不使用String和Integer实例。该问题的一个指令是限制内存使用。在到目前为止的每个答案中，对内存产生了重大影响（转换为 Integer 和 String ）。

Given the constraints on the problem, the more efficient way to solve this problem is to not use String and Integer instances at all. One of the directives of the problem is to limit memory usage. In each of the answers so far, there has been a significant impact on memory (converting to and from Integer and String).

这是一个可能更快的解决方案，并且根本不分配堆内存（尽管它有递归，所以它可能有一些堆栈效应 - 关于与 Arrays.sort（）相同。这解决了第一原理的问题，它没有为结果分配单独的数组，因此，与其他解决方案相比，它相对较长，但是，那些其他解决方案隐藏了该解决方案所没有的大量复杂性。 。

Here is a solution that is likely to be faster, and allocates no heap memory at all (although it has recursion so it may have some stack-effect - about the same as Arrays.sort()). This solves the problem from first-principles, it does not allocate a separate array for the results, and thus, it is relatively long compared to other solutions, but, those other solutions hide a mass of complexity that this solution does not have...

// this compare works by converting both values to be in the same 'power of 10',
// for example, comparing 5 and 20, it will convert 5 to 50, then compare 50 and 20
// numerically.
public static final int compareLexographicallyToLimit(final int limit, int a, int b) {
    if (a == b) {
        return 0;
    }
    if (a > limit || b > limit || a < 0 || b < 0) {
        return a > b ? 1 : -1;
    }

    int max = Math.max(a, b);
    int nextp10 = 1;
    while (max > 10) {
        max /= 10;
        nextp10 *= 10;
    }
    while (a < nextp10) {
        a *= 10;
    }
    while (b < nextp10) {
        b *= 10;
    }
    return a > b ? 1 : -1;
}

private static void sortByRules(final int[] input, final int limit, final int from, final int to) {
    if (from >= to) {
        return;
    }
    int pivot = from;
    int left = from + 1;
    int right = to;
    while (left <= right) {
        while (left <= right && compareLexographicallyToLimit(limit, input[left], input[pivot]) <= 0) {
            left++;
        }
        while (left <= right && compareLexographicallyToLimit(limit, input[pivot], input[right]) <= 0) {
            right--;
        }
        if (left < right) {
            int tmp = input[left];
            input[left] = input[right];
            input[right] = tmp;
            left++;
            right--;
        }
    }
    int tmp = input[pivot];
    input[pivot] = input[right];
    input[right] = tmp;
    sortByRules(input, limit, from, right-1);
    sortByRules(input, limit, right+1, to);

}

public static void main(String[] args) {
    int[] input = {2,3,5,7,11,13,17,19,31,37,41, 43, 100};
    sortByRules(input, 40, 0, input.length - 1);
    System.out.println(Arrays.toString(input));
    sortByRules(input, 15, 0, input.length - 1);
    System.out.println(Arrays.toString(input));
}

这篇关于按字典顺序对int数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！