An example of the maximum number index in an array with probability 1 / (the number of maximum numbers)

Question

This is one of the recent issues I came across. The program returns the index of the maximum number in the array [Note: the array may or may not contain several copies of the maximum number], so each index (which contains the maximum numbers) has a probability of 1 / no maximum numbers to return.

Examples:

• [- 1 3 2 3 3], each of the positions [1,3,4] has a 1/3 probability of return (three 3s)
• [2 4 6 6 3 1 6 6], each of [2,3,6,7] has a 1/4 probability of return (which corresponds to position 6s).

First, I gave O (n) time and O (n) a spatial algorithm, where I collect a set of maximum indices and then return a random number from the set. But he asked for a program of O (n) and O (1) complexity, and then I came up with this.

int find_maxIndex(vector<int> a) { max = a[0]; max_index = 0; count = 0; for(i = 1 to a.size()) { if(max < a[i]) { max = a[i]; count = 0; } if(max == a[i]) { count++; if(rand < 1/count) //rand = a random number in the range of [0,1] max_index = i; } } return max_index; } 

I gave him this decision. But I doubt that if this procedure chooses one of the indices of maximum numbers with equal probability. I hope I get it. Is there any other way to do this?

Answer 1

Your algorithm works fine, and you can prove it using induction.

That is, if it works for any array of size N , prove that it works for any array of size N+1 .

So, given an array of size N+1 , think of it as a sub-array of size N , and then a new element at the end. By assumption, your algorithm evenly selects one of the maximum elements of the submatrix ... And then it behaves as follows:

If the new item is greater than the max sub-array, return that item. This is certainly correct.

If the new item is less than max for the submatrix, return the result of the algorithm to the submatrix. Also obviously correct.

The only slightly difficult part is when the new element is equal to the maximum element of the submatrix. In this case, let the number of maximal elements in the subarray be k . Then, by condition, your algorithm chose one of them with a probability of 1/k . Keeping the same element with probability k/(k+1) , you make the total probability of choosing the same element equal to 1/k * k /(k+1) == 1/(k+1) , as you wish. You also select the last item with the same probability, so we are done.

To complete the inductive proof, just check if the algorithm works on an array of size 1. In addition, for the quality of the goals, correct it so that it does not break into arrays of zero size :-)

[Update]

By the way, this algorithm and its proof are closely related to the Fisher-Yates shuffle (which I always considered the “Knut map drag and drop algorithm”, but Wikipedia says I'm lagging behind).

Answer 2

You have Sampling tanks ! There is another clear solution, but two passes are required.

 int find_maxIndex(vector<int> a){ int count = 1; int maxElement = a[0]; for(int i = 1; i < a.size(); i++){ if(a[i] == maxElement){ count ++; } else if(a[i] > maxElement){ count = 1; maxElement = a[i]; } } int occurrence = rand() % count + 1; int occur = 0; for(int i = 0; i < a.size(); i++){ if(a[i] == maxElement){ occur++; if(occur == occurrence) return i; } } } 

The algorithm is quite simple, first find the number of times that the maximum element occurs in the first pass. And select a random occurrence and return the index of this event. It takes two passes, but is very easy to understand.

Answer 3

The idea is sound, but the devil is in the details.

First, what language do you use? It can make a difference. rand() from C and C ++ will return an integer that is unlikely to be less than 1/count if it does not return 0 , Even if 1/count is an integer division, this result will always be 0 .

Your account is also turned off by 1. It starts at 1 when you get a new max, but you immediately increase it in the following if .