Most elements in the Divide-And-Conquer O (N.log (N)) array

Question

An array a [] containing N elements that can be repeated is called "contain the element av mainly" if more than half of its contents is equal to v. Given the array a [], it is intended to create an efficient algorithm (at the time of N.log (N) and the use of divide-and-conquer) to check whether it contains a majority element and determine it. Consider the only available comparison operation between array elements - equality (a [i] == a [j]), performed in constant time. (Hint: in the algorithm, divide the array into [] into two subarrays a1 [] and a2 [], each half the size of []. If the element in most [] is v, then v must also be the element in most a1 [] or a2 [] or both).

int main() { int a[12] = {5, 9, 3, 13, 5, 21, 5, 7, 17, 12, 5, 6}; int N = 12, lo = 0, hi = N - 1, mid,i,j; mid = lo + (hi - lo) / 2; int n1 = mid - lo + 1; int n2 = hi - mid; int a1[n1],a2[n2]; /* Copy data to temp arrays a1[] and a2[] */ for (i = 0; i < n1; i++) a1[i] = a[lo + i]; for (j = 0; j < n2; j++) a2[j] = a[mid+1+j]; while (i < n1 && j < n2) { if(a1[i]==a2[j]){ }else if(){ }else{ } } return 0; } 

I am having problems along the way in which I have to continue working with equality by comparing auxiliary arrays to see if the element itself is on a1 [] or a2 [] or both!

Answer 1

I think the function should:

1) Call yourself recursively for the first half of the array (returns the answer a)

2) Call yourself recursively for the second half of the array (returns answer b)

3) Scroll through the array and count the number of a / b matches and return depending on what most matches have

Please note: there is no need to copy the array at any stage, because it never changes, just pass the index to the beginning and length of the subarray.

Answer 2

Here is a Python implementation that matches the description (sorry, I don't understand C, but I think it's pretty simple code). We can track the registered return values ​​and indexes for each section in question to understand how it works.

 # Returns v if v is a majority; # otherwise, returns None def f(arr, low, high): if low == high: return arr[low] if low + 1 == high: return arr[low] if arr[low] == arr[high] else None n = high - low + 1 mid = (low + high) / 2 l = f(arr, low, mid) r = f(arr, mid + 1, high) print 'n: ' + str(n) + '; l: ' + str(l) + '; r: ' + str(r) + '; L: ' + str((low, mid)) + '; R: ' + str((mid + 1, high)) if l == r: return l counts = [0, 0] for i in xrange(low, high + 1): if arr[i] == l: counts[0] = counts[0] + 1 if arr[i] == r: counts[1] = counts[1] + 1 if l and counts[0] * 2 > n: return l if r and counts[1] * 2 > n: return r return None 

Output:

 a = [5, 9, 3, 5, 5, 21, 5, 7, 17, 5, 5, 5] print f(a, 0, len(a) - 1) """ n: 3; l: None; r: 3; L: (0, 1); R: (2, 2) n: 3; l: 5; r: 21; L: (3, 4); R: (5, 5) n: 6; l: None; r: 5; L: (0, 2); R: (3, 5) n: 3; l: None; r: 17; L: (6, 7); R: (8, 8) n: 3; l: 5; r: 5; L: (9, 10); R: (11, 11) n: 6; l: None; r: 5; L: (6, 8); R: (9, 11) n: 12; l: None; r: 5; L: (0, 5); R: (6, 11) 5 """ 

Answer 3

This is probably not the answer you are looking for. But there is an interesting probabilistic approach to this problem. You can select a specific x position of the array and count the number of occurrences of the array [x] to see if it appears> = array.size () / 2.

If there is an element that fills more than half of the array, the probability of randomly choosing its position is> 1/2 for each iteration.

So, if you do something like 30 iterations, the probability of choosing the “dominant” element is (1 - (1/2) ^ 30), which is suitable for almost every application.

Difficulty - O (numberOfIterations * arraySize)

Here is the code (:.

This is in C ++, but I'm sure you can translate it into C without much effort.

 #include <vector> #include <iostream> int arraySize, numberOfIterations; int count(int element, std::vector<int>& array) { int count = 0; for(const int& number : array) { count += (number == element); } return count; } int main(){ srand(time(0)); std::cin >> arraySize; std::vector<int> arr(arraySize); for(int i = 0; i < arraySize; ++i) { std::cin >> arr[i]; } std::cin >> numberOfIterations; for(int i = 0; i < numberOfIterations; ++i) { int idx = rand() % arraySize; int freq = count(arr[idx], arr); //std::cout << idx << std::endl; if(freq > arraySize / 2) { std::cout << "The element = " << arr[idx] << " dominates the array provided " << std::endl; return 0; } } return 0; }