Thursday, February 19, 2015

Find second largest element in an unsorted array

Construct a tree and find the largest element by pairwise comparison ( I use a 2D array).
Back track all the elements that have been compared with the maximum.
Total comparison:
find the maximum: n /2 + n / 4 + ... n / k = n - 1, where k is the depth of the tree
find the second maximum log2n - 1 (1 comparison each layer)


public static int secondLargest(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Null or empty array!");
  int[][] arrayTree = getTree(array);
  int maxEle = arrayTree[arrayTree.length - 1][0];
  int maxPos = 0;
  int secondMax = Integer.MIN_VALUE;
  for (int i = arrayTree.length - 2; i >= 0; i--) {
   maxPos = arrayTree[i][maxPos * 2] == maxEle ? maxPos * 2 : maxPos * 2 + 1;
   if (arrayTree[i].length % 2 != 0 && maxPos == arrayTree[i].length - 1) {
    //System.out.println(i);
    continue;
   }
   //the position of the potential second max
   //if max position is at odd index, second max = maxPos - 1;
   //else maxPos + 1
   int secondPos = maxPos % 2 == 0 ? maxPos + 1 : maxPos - 1;
   secondMax = Math.max(secondMax, arrayTree[i][secondPos]);
  }
  return secondMax;
 }
 private static int[][] getTree(int[] array) {
  int depth = (int)Math.ceil((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++) {
   int length = tree[i - 1].length % 2 == 0 ? tree[i - 1].length / 2 : tree[i - 1].length / 2 + 1;
   tree[i] = new int[length];
   int index = 0;
   for (int j = 0; j < tree[i - 1].length - 1; j += 2) {
    tree[i][index] = Math.max(tree[i - 1][j], tree[i - 1][j + 1]);
    index++;
   }
   if (index < length)
    tree[i][index] = tree[i - 1][tree[i - 1].length - 1];
  }
  return tree;
 }

No comments:

Post a Comment