Candidate to search for a control in an array

Question

I do not ask how to find the major element in the array , which is described in detail here Find the majority element in the array

My problem is this:

There is an arr[1...2n] array arr[1...2n] , an element of most of this maj array, now I will use the following rule to delete elements in arr ,

if arr[i] == arr[i + 1] , delete arr[i] , i = 1, 3, 5, ..., 2n - 1; else if arr[i] != arr[i + 1] , delete both arr[i] and arr[i + 1] , i = 1, 3, 5, ..., 2n - 1.

then we can get a new array new_arr , and the candidate control for new_arr is new_maj , is there any evidence that new_maj == maj ?

Answer 1

Yes, there is evidence.

We are only interested in pairs of elements a[i],a[i+1] , i odd. If a[i]=a[i+1] , we call such a pair “good”. Other couples are "bad." Elements that are equal to most candidates are groovy. A good pair of groovy elements is a pair of groovy.

The simple fact about good pairs is that at least one half of the groovy good pairs. Suppose this is not so; then among good pairs there are strictly less than half of the groovy elements, and among bad pairs no more than half of the groovy elements. Overall, strictly less than half the groovy items. This is a contradiction.

So, we found that at least one half of the good groovy pairs.

Now eliminate all the bad fumes. At least one half of all groovy elements (because only good pairs remain, and at least half of them are groovy).

Now eliminate all other elements from the good pairs. At least one half of all groovy items (because the amount of each item simply halves).

This completes the proof.

Answer 2

Define N = 2 n . The array contains elements of N

Define M as the number of maj arrays appears in the array. The definition of "majority element" is that M > N/2 .

Now divide the array into pairs p[1] ... p[n] . Define q0 as the number of pairs containing zero instances of maj . Define q1 as the number of pairs that contain exactly one instance of maj . Define q2 as the number of pairs that contain exactly two maj instances.

Then N = 2 q0 + 2 q1 + 2 q2 and M = q1 + 2 q2 .

We substitute in the inequality that defines the element of the majority, and simplify:

  M > N / 2 q1 + 2 q2 > (2 q0 + 2 q1 + 2 q2) / 2 q1 + 2 q2 > q0 + q1 + q2 2 q2 > q0 + q2 q2 > q0 

Thus, the number of pairs containing two maj instances exceeds the number of pairs containing zero maj instances.

Now define M' number of times maj in the new array after running your algorithm. The algorithm removes one maj for each pair q1 and one maj for each pair q2 . So, M' = M - q1 - q2 .

Define N' as the size of the new array created by the algorithm. The algorithm removes two elements for each pair q1 and one element for each pair q2 .

But we do not know how many elements the algorithm removes for each pair q0 . Some q0 pairs contain two different elements, and the algorithm removes both. But other q0 pairs contain the same (not maj ) elements, and the algorithm removes only one.

One extreme is that all q0 pairs are completely removed. In this case, the algorithm removes the elements 2 q0 , therefore

 N - 2 q1 - q2 - 2 q0 ≤ N' 

Another extreme point is that only one element is removed from each pair q0 . In this case, the algorithm removes the elements q0 , therefore

 N - 2 q1 - q2 - q0 ≥ N' 

Let's go back to the definition of "majority element" and make some algebra:

  M > N / 2 M - q1 - q2 > N / 2 - q1 - q2 M - q1 - q2 > (N - 2 q1 - 2 q2) / 2 M - q1 - q2 > (N - 2 q1 - q2 - q2) / 2 

Left side M' .

 M' > (N - 2 q1 - q2 - q2) / 2 

Can we turn the right side into N' / 2 ? First, multiply both sides by 2:

 2 M' > N - 2 q1 - q2 - q2 

Recall that we have proved q2 > q0 . therefore

 2 M' > N - 2 q1 - q2 - q2 > N - 2 q1 - q2 - q0 

and, since we deduced N - 2 q1 - q2 - q0 ≥ N' ,

 2 M' > N - 2 q1 - q2 - q0 ≥ N' 

So

 2 M' > N' M' > N' / 2 

Thus, maj appears enough times in the new array as an element of most of the new array. Q.E.D.

Answer 3

Here is my version of the proof:

Consider 4 cases for the pairs arr [i] and arr [i + 1] (or vice versa, the order with the pair is not important), I'm odd. Let maj be the main element and min be any minor element:

• maj maj - let the number of such pairs be
• maj min - let the number of such pairs be b
• min1 min2 - let the number of such pairs be c, min1! = min2
• min1 min1 - let the number of such pairs be d

a, b, c, d all> = 0.

Case 1 contributes 2 to the original sum of the basic elements | May | and reduces the final amount of basic elements | maj | '(after running the algorithm) by 1

Case 2 contributes 1 to | May | and from 1 to | min |, the initial sum of all minor elements and decreases | maj | 'on 1 and | min | 'on 1

Case 3 contributes 2 to | min | and decreases | min | ' on 2

Case 4 contributes 2 to | min | and decreases | min | 'on 1

Therefore, the total number of basic elements in the original arr [] array is:

 |maj| = 2a + b 

So far, the number of all minor elements:

 |min| = b + 2c + 2d 

Since | maj | > | min |,

 2a + b > b + 2c + 2d 2a > 2c + 2d a > c + d 

After starting the algorithm, a new number of basic elements is determined:

 |maj|' = |maj| - a - b 

and the new number of minor elements:

 |min|' = |min| - b - 2c - d 

Substituting, we get:

 |maj|' = 2a + b - a - b = a |min|' = b + 2c + 2d - b - 2c - d = d 

Since we know from above that c + d <a, a, c, d are all> = 0, we have

 a > c + d => a > d => |maj|' > |min|' 

Therefore, maj is still the main element of the new array.