Given an unsorted array, extract the second max/min using the least number of comparison
The total comparisons will be n + log n - 2. The algorithm is called tournament method. A detailed explanation can be found here. I simplified this guy's implementation.
public static int secondMax(int[] array) { if (array == null || array.length == 0) throw new IllegalArgumentException("Null or empty array"); int[][]tree = reverseTree(array); int secondMax = Integer.MIN_VALUE; int max = tree[tree.length - 1][0]; int rootPos = 0; for (int i = tree.length - 2; i >= 0; i--) { rootPos = tree[i][rootPos * 2] == max ? rootPos * 2 : (rootPos * 2 + 1); if (i < tree.length - 2 && rootPos == tree[i].length - 1) continue; if (rootPos % 2 == 0) { secondMax = Math.max(secondMax, tree[i][rootPos + 1]); } else secondMax = Math.max(secondMax, tree[i][rootPos - 1]); } return secondMax; } private static int[][] reverseTree(int[] array) { int depth = (int)Math.ceil((double)Math.log((double)array.length)/Math.log(2.0)) + 1; int[][] tree = new int[depth][]; tree[0] = array; for (int i = 1; i < depth; i++) { tree[i] = getRow(tree[i - 1]); } return tree; } private static int[] getRow(int[] lastRow) { int length = (lastRow.length % 2 == 0) ? (lastRow.length/ 2) : (lastRow.length / 2 + 1); int[] currRow = new int[length]; int index = 0; for (int i = 0; i < lastRow.length - 1; i += 2) { if (lastRow[i] < lastRow[i + 1]) currRow[index] = lastRow[i + 1]; else currRow[index] = lastRow[i]; index++; } if (index < currRow.length) { currRow[index] = lastRow[lastRow.length - 1]; } return currRow; }
Note:
I tried to use a map at first to make it easier, it gave me ConcurrentModificationException, and it's second time. Yeah, I will remember never try to modify a map in a loop...
Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.
Just to make life easier, this method finds both max and min at the same time.
public static int[] maxNMin(int[] array) { if (array == null || array.length == 0) throw new IllegalArgumentException("Null or empty array!"); return findLimits(array, 0, array.length - 1); } private static int[] findLimits(int[] array, int start, int end) { int[] limits = new int[2]; if (end - start <= 0) { limits[0] = array[start]; limits[1] = array[start]; return limits; } if (end - start == 1) { if (array[start] < array[end]) { limits[0] = array[start]; limits[1] = array[end]; } else { limits[0] = array[end]; limits[1] = array[start]; } return limits; } int mid = (start + end) / 2; int[] leftLimits = findLimits(array, start, mid); int[] rightLimits = findLimits(array, mid + 1, end); if (leftLimits[0] < rightLimits[0]) limits[0] = leftLimits[0]; else limits[0] = rightLimits[0]; if (leftLimits[1] > rightLimits[1]) limits[1] = leftLimits[1]; else limits[1] = rightLimits[1]; return limits; }
Given an unsorted array, extract the max and min value using the least number of comparisonUse pairwise comparison, 3 comparisons for 2 elements, so total 3/2 * n comparisons. See here.
public static int[] limit(int[] array) { if (array == null || array.length == 0) throw new IllegalArgumentException("Wrong input!"); int max = array[0]; int min = array[0]; int start = 0; if (array.length % 2 != 0) start = 1; for (int i = start; i < array.length - 1; i += 2) { if (array[i] < array[i + 1]) { max = Math.max(max, array[i + 1]); min = Math.min(min, array[i]); } else { max = Math.max(max, array[i]); min = Math.min(min, array[i + 1]); } } int[] limits = new int[2]; limits[0] = min; limits[1] = max; return limits; }
No comments:
Post a Comment