This is one problem introduced in "Introduction to Algorithm".
We can use radix-sort to solve it.
package alg;
import java.util.ArrayList;
import java.util.Iterator;
/*
* This example shows how to use radix sort algorithm to sort N integers in the range of 0 ~ N^2-1.
*/
public class RadixSortExample {
void sort(int a[], int N){
int len = a.length;
ArrayList<ArrayList<Integer>> bucket= new ArrayList<ArrayList<Integer>>(N);
for(int i = 0; i<N;i++){
bucket.add(new ArrayList<Integer>(len));
}
ArrayList<Integer> temp = new ArrayList<Integer>(len);
for(int i = 0; i< len; i++){
temp.add(new Integer(a[i]));
}
for(int i = 0; i<len; i++){
int digit0 = temp.get(i).intValue() % N;
bucket.get(digit0).add(temp.get(i));
}
temp.clear();
for(int i = 0; i<N; i++){
Iterator<Integer> it = bucket.get(i).iterator();
while(it.hasNext()) temp.add(it.next());
}
for(int i = 0; i<N;i++){
bucket.get(i).clear();
}
for(int i = 0; i<len; i++){
int digit1 = temp.get(i).intValue() / N;
bucket.get(digit1).add(temp.get(i));
}
temp.clear();
for(int i = 0; i<N; i++){
Iterator<Integer> it = bucket.get(i).iterator();
while(it.hasNext()) temp.add(it.next());
}
Iterator<Integer> it = temp.iterator();
while(it.hasNext()) System.out.println(it.next());
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a []= {63,20,43,15,56,9,1,28};
RadixSortExample r = new RadixSortExample();
r.sort(a,8);
}
}
分享到:
相关推荐
The range of reals in PDF A is the same as SkFixed: + - 32,767 and + - 1 65,536 (though integers can range 2^31 - 1 to -2^31).
| _O(2^n)_ | _O(n)_ | Hard | 馃摉 | 421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an...
In this paper, we study the cross-correlation between a binary m-sequence (st) of length 2^m-1 and its d-decimated sequences (s_{dt+u}); 0<=u < 2k+13 : It is shown that the maximum magnitude of...
Each line contains the length of time to complete the chore, the number of the prerequisites, Pi, (0 ), and the Pi prerequisites (range 1..N, of course). Output A single line with an integer ...
leetcode伪代码find-n-unique-integers-sum-up-to-zero 题目解读: 题目来源: 原文: Given an integer n, return any array containing n unique integers such that they add up to 0. 解读: 给定一个正整数n, ...
The cow bicycling team consists of N (1 <= N ) cyclists. They wish to determine a race strategy which will get one of them across the finish line as fast as possible. Like everyone else, cows race ...
c iruf = roughness measure, 0 (size penalty), 1 (1st deriv.), 2 (2nd deriv.) c nit = current iteration number (0=start) c i = loop index c itmax = maximum iteration number c konv = convergence flag ...
Column 1: Programs for sorting integers bitsort.c -- Sort with bit vectors. sortints.cpp -- Sort using C++ STL sets. qsortints.c -- Sort with C library qsort. bitsortgen.c -- Generate random ...
比如,图像数据为 7 14 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 0 0 0 0 0 0 0 0 255 255 255 255 255 255 0 255 255 255 255 255 255 0 255 255 255 255 255 255 0 255 255 255 255 ...
2) Type in or Paste the number in the Editbox for the Modulus (N). This enables the 'Factor' button. 3) Press the Factor N button. Note that factoring numbers > 240 Bits can take a LOT of time and...
The input will consist of a series of integers n, one integer per line. For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit ...
2 和 c leetcode 1304 - 找到 N 个唯一整数总和为零 C# public int [] SumZero ( int n ) { var arr = new int [ n ]; int j = 0 ; int x = 1 ; for ( int i = 0 ; i < n / 2 ; i ++ ) { arr [ j ++ ] = x ; arr...
There is two integers N, M (1<=N, M) separated by one white space in the first line of each block, representing the size of the 2-D array. Then N lines follow, each line contains M integers ...
But, as The Irrationals shows, these are the real "complex" numbers, and they have an equally complex and intriguing history, from Euclid's famous proof that the square root of 2 is irrational to ...
Given two integers n and m, count the number of pairs of integers (a,b) such that 0 < a < b < n and (a^2+b^2 +m)/(ab) is an integer. This problem contains multiple test cases! The first line of a ...
Next, there is a line of n integers specifying fi (1 <= i <=n), then a line of n integers di (1 <=i <=n), and finally, a line of n - 1 integers ti (1 <=i <=n - 1). Input is terminated by a case in ...
Both s and t are integers, 1 <= s <= 90 and 1 <= t <= 12. The values for t are always in strictly increasing order. A value of -1 for n signals the end of the input. Output For each input set, ...
主要介绍数字图像处理的基本操作 以下是其中一部分程序: function I = isinteger(A) %ISINTEGER Determines which elements of ... -2 -1 0 1 2 . . . )in A, and 0s (FALSE) elsewhere. % A must be a numeric array.
Function of an integer raised in a power and the calculation of the sum of a series of integers (1^e+2^e....+n^e) raised in a power.
The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N When N is 0, it indicates test to end. 输出格式 Output must contain ...