Geek asks and answers

Find all occurrences of the maximum value in an unsorted list - one pass with read only memory

This question was asked to me in an interview. Given an unsorted list of integers, if you can find all occurrences of the maximum value in linear time and read-only memory.

I could not answer this then and came across a median algorithm of medians. Still not sure if this algorithm is applicable in this case.

+3
source share
6 answers

You can find the maximum set value in O (n). Just scroll through the list and update max:

max = int_array[0]
for i = 1 to int_array.size():
    if int_array[i] > max:
        max = int_array[i]

In the next pass, you can invoke the desired functionality for each such element. For instance. if you want to print your position and finally their score:

count = 0
for i = 0 to int_array.size():
    if int_array[i] == max:
        print "Index i"
        count += 1
print count

, , , , (, ), . . , :

count = 1
max = int_array[0]
indexes = [0]
for i = 1 to int_array.size():
    if int_array[i] == max:
        count += 1
        indexes.insert(i)
    else if int_array[i] > max:
        count = 1
        indexes = [i]
        max = int_array[i]
print "There are " + count + " elements with maximal value of " + max
print "On positions: "
for int i = 0 to count:
    print indexes[i]
+3

, :

set POS //where the maxima are, initially empty
max = A[1]//first element
add 1 to POS

for i = 2 to n
  if A[i] > max
    max = A[i]
    empty POS
    add i to POS
  if A[i] == max
    add i to POS

return POS

O(n + count(max)), O(n), .

+2

, .

O(n), . , , O(1) . *

numbers = [ ... list of numbers ... ]
largest_seen = - Infinity
positions_seen_at = [ empty list ]

for ( i = 0; i < len(numbers); i++ ):
    if numbers[i] > largest_seen:
        largest_seen = numbers[i]
        positions_seen_at = [ empty list ]

    if numbers[i] == largest_seen:
        positions_seen_at.append(i)

* "" . , . O(log n) .

+2

,

Python, L, ,

L.count(max(L))

L.count - O (n)
max (L) O (n)

, - O (n)

+1

Thanks to everyone for such detailed answers. After a little thought, I think I have a solution that gives you the maximum and all occurrences of the maximum element in a single pass in an unsorted list. Alas!! I could have come up with a couple of days ago :) but better late than never ...

Here is the java code snippet I wrote:

public int getNumberOfOccurrencesOfMax(List<Integer> inputList){ 

if(this.inputList.size() == 0) 
     return 0;
Integer max = Integer.MIN_VALUE, max_occurances = 0;

for(int i=0; i < inputList.size(); i++){
        if(max < this.inputList.get(i)){
            max = this.inputList.get(i);
            max_occurances = 1;
        }
        else if(max > this.inputList.get(i)){
            max_occurances = (max_occurances > 0) ? max_occurances : 1; 
        }
        else{
            max_occurances += 1;
        }
    }
return max_occurances;
} // END_OF_METHOD

I tried the code with an example list (1,1,2,2,3,4,4,5,5,5).

Feel free to suggest any improvements over my implementation.

Best

+1
source

I think this will work too:

O (n) algorithm

i = 0
highestStart = 0
size = array.size
for i < size -1 
     if array[i] > array[i+1]
          x = array[i]
          delete array[i] //remove higher value
          array[array.size] = x  // push higher value to the end
          highestStart = i
      else if array[i] < array[i+1]
          highestStart = i+1
     end if
  end if
  i = i+1
end for
return subarray[highestStart, array.size -1]

1*,5*,4 ,7 ,9 ,4 ,9   :0,1
1 ,5*,4*,7 ,9 ,4 ,9   :1,2
1 ,4 ,7*,9*,4 ,9 ,5   :2,3
1 ,4 ,7 ,9*,4*,9 ,5   :3,4
1 ,4 ,7 ,4 ,9*,5*,9   :4,5
1 ,4 ,7 ,4 ,5 ,9*,9*  :5,6
0
source

More articles:


All Articles