Skip to content

Instantly share code, notes, and snippets.

@evisong
Created February 27, 2012 13:56
Show Gist options
  • Select an option

  • Save evisong/1923939 to your computer and use it in GitHub Desktop.

Select an option

Save evisong/1923939 to your computer and use it in GitHub Desktop.
Concatenation of array elements into an integer with the maximum value (Java porting)
package me.evis.lab.algorithm;
import java.util.Arrays;
import java.util.Comparator;
import org.apache.commons.lang.ArrayUtils;
/**
* Port from https://gist.github.com/1921701#file_concatenate_integers.c
*/
public class ConcatenateIntegers {
private static final int LEN = 10;
private CustomComparator comparator = new CustomComparator();
public static void main(String[] args) {
ConcatenateIntegers main = new ConcatenateIntegers();
main.testCompare();
main.testSort();
}
private void testCompare() {
assert (comparator.compare(10, 10) == 0);
assert (comparator.compare(12, 10) > 0);
assert (comparator.compare(52, 57) < 0);
assert (comparator.compare(5, 57) < 0);
assert (comparator.compare(6, 637) > 0);
assert (comparator.compare(6, 637) > 0);
assert (comparator.compare(23, 231) > 0);
assert (comparator.compare(23, 232) == 0);
assert (comparator.compare(23, 233) < 0);
}
private void testSort() {
int[] a1 = { 1, 23, 3, 2, 345, 341, 34 };
sort(a1);
int[] a2 = { 78, 80, 71, 77, 79 };
sort(a2);
int[] a3 = { 2, 1, 39, 5 };
sort(a3);
int[] a4 = { 98, 987, 8, 9, 99 };
sort(a4);
}
/**
* Sort an integer array to the maximum value of the big integer resulted by
* concatenating all the array elements. For example, concatenating [1, 2,
* 39, 5] results 53921.
*/
private void sort(int[] array) {
int count = array.length;
int i;
Integer[] tempArray = ArrayUtils.toObject(array);
Arrays.sort(tempArray, comparator);
for (i = count - 1; i >= 0; i--) {
System.out.println(tempArray[i]);
}
System.out.println("");
}
private class CustomComparator implements Comparator<Integer> {
private int[] arrayA = new int[LEN], arrayB = new int[LEN];
/**
* The tricky part is when two integers a and b don't have the same
* length:
*
* a: x_1 x_2 ... x_n y z_1 z_2 ... z_m
* b: x_1 x_2 ... x_n
*
* There are two combination of a and b:
*
* ab: x_1 x_2 ... x_n y ...
* ____________________^____
* ba: x_1 x_2 ... x_n x_1 ...
* ____________________^______
*
* The comparison of ab and ba is determined by the comparison of y and
* x_1
*/
@Override
public int compare(Integer a, Integer b) {
int countA, countB, iA, iB, diff;
countA = reverse(a, arrayA);
countB = reverse(b, arrayB);
for (iA = iB = 0; iA < countA && iB < countB; iA++, iB++) {
diff = arrayA[iA] - arrayB[iB];
if (diff != 0)
return diff;
}
if (iA == countA && iB == countB) {
return 0;
}
if (iA < countA) {
return arrayA[iA] - arrayA[0];
}
return -(arrayB[iB] - arrayB[0]);
}
private void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
// Not take 0 into account
private int reverse(int n, int array[]) {
int i, j;
i = 0;
while (n > 0) {
array[i++] = n % 10;
n /= 10;
}
for (j = 0; j < i / 2; j++) {
swap(array, j, i - j - 1);
}
return i;
}
}
}
@yaojingguo
Copy link

Java version is more readable.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment