Created
February 27, 2012 13:56
-
-
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Java version is more readable.