• API
• FAQ
• Tools
• Archive
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.

Top