java – 按字典顺序对int数组进行排序
发布时间：2020-12-15 04:15:59 所属栏目：Java 来源：网络整理
导读：我遇到了一个问题： 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. 获得主要号码很容易.但我无法找出一种有效的整数数组排序方法. public sta
|
我遇到了一个问题：
获得主要号码很容易.但我无法找出一种有效的整数数组排序方法. 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,7,11,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).
这是一个可能更快的解决方案,并且根本不分配堆内存(尽管它具有递归,因此它可能具有一些堆栈效果 – 与Arrays.sort()大致相同).这解决了第一原理的问题,它没有为结果分配单独的数组,因此,与其他解决方案相比,它相对较长,但是,那些其他解决方案隐藏了该解决方案所没有的大量复杂性. . // 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,right+1,to);
}
public static void main(String[] args) {
int[] input = {2,41,43,100};
sortByRules(input,40,input.length - 1);
System.out.println(Arrays.toString(input));
sortByRules(input,15,input.length - 1);
System.out.println(Arrays.toString(input));
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |