Saturday 4 June 2016

Find the maximum repeating number in O(n) time and O(1) extra space

public class FindMaxRepeat {

   private static int maxRptElmt(int[] array, int k) {
      for(int i=0;i<array.length;i++) {
         array[array[i]%k] += k;
      }

      int max = Integer.MIN_VALUE;
      int index = -1;

      for(int i=0;i<array.length;i++) {
         if(max<array[i]) {
            max = array[i];
            index = i;
         }
      }

      /* restore the original array. */
      for (int i = 0; i< array.length; i++) {
         array[i] = array[i]%k;
      }
      return index;
   }
  
   public static void main(String[] args) {
      int[] array = {1,2,3,4,5,6,7,1,2,3,4,5,6,9,1,2,2};
      int k = array.length;
      int maxRpt = maxRptElmt(array, k);
      System.out.println(maxRpt);
   }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...