daily pastebin goal
41%
SHARE
TWEET

Untitled

a guest Feb 19th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. element x;
  2. int count ← 0;
  3. For(i = 0 to n − 1) {
  4.   if(count == 0) { x ← A[i]; count++; }
  5.   else if (A[i] == x) count++;
  6.   else count−−;
  7. }
  8. Check if x is dominant element by scanning array A
  9.    
  10. static int dominant(final int... set) {
  11.   final int[] freqs = new int[Integer.MAX_VALUE];
  12.   for (int n : set) {
  13.     ++freqs[n];
  14.   }
  15.   int dom_freq = Integer.MIN_VALUE;
  16.   int dom_idx = -1;
  17.   int dom_n = -1;
  18.   for (int i = set.length - 1; i >= 0; --i) {
  19.     final int n = set[i];
  20.     if (dom_n != n) {
  21.       final int freq = freqs[n];
  22.       if (freq > dom_freq) {
  23.         dom_freq = freq;
  24.         dom_n = n;
  25.         dom_idx = i;
  26.       } else if (freq == dom_freq) {
  27.         dom_idx = -1;
  28.       }
  29.     }
  30.   }
  31.   return dom_idx;
  32. }
  33.    
  34. public int dominator(int[] A) {
  35.     int N = A.length;
  36.  
  37.     for(int i = 0; i< N/2+1; i++)
  38.     {
  39.         int count=1;
  40.         for(int j = i+1; j < N; j++)
  41.         {
  42.             if (A[i]==A[j]) {count++; if (count > (N/2)) return i;}
  43.         }
  44.     }
  45.  
  46.     return -1;
  47.   }
  48.    
  49. public Integer findDominator(int[] arr) {
  50.     int[] arrCopy = arr.clone();
  51.  
  52.     Arrays.sort(arrCopy);
  53.  
  54.     int length = arrCopy.length;
  55.     int middleIndx = (length - 1) /2;
  56.  
  57.     int middleIdxRight;
  58.     int middleIdxLeft = middleIndx;
  59.  
  60.     if (length % 2 == 0) {
  61.         middleIdxRight = middleIndx+1;
  62.     } else {
  63.         middleIdxRight = middleIndx;
  64.     }
  65.  
  66.     if (arrCopy[0] == arrCopy[middleIdxRight]) {
  67.         return arrCopy[0];
  68.     }
  69.  
  70.     if (arrCopy[middleIdxLeft] == arrCopy[length -1]) {
  71.         return arrCopy[middleIdxLeft];
  72.     }
  73.  
  74.     return null;
  75. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top