3

这个问题是在一次采访中问我的。给定一个未排序的整数列表，如果可以在线性时间和常量内存中找到所有出现的最大值。

我当时无法回答，遇到了中位数算法的中位数。仍然不确定该算法是否适用于这种情况。

4

6 回答 6

3

您可以在 O(n) 中找到集合的最大值。只需浏览列表并更新最大值：

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

在下一轮中，您可以在每个此类元素上调用所需的功能。例如，如果你想打印出他们的位置，最后是他们的计数：

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]
于 2012-05-14T06:26:55.607 回答
2

这是一个单遍解决方案，它记录了所有最大值实例的位置：

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)，因为您必须存储所有出现最大值的位置。

于 2012-05-14T07:57:33.903 回答
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)记忆。

于 2012-05-14T08:18:11.213 回答
1

谢谢大家这么详细的回答。经过一番思考，我想我有一个解决方案，它可以在未排序的列表中一次性为您提供最大项目的最大值和所有出现的最大值。唉！！我本可以在几天前想出它:)但迟到总比没有好......

这是我写的java代码片段：

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

我用（1,1,2,2,3,4,4,5,5,5）的示例列表尝试了代码。

随时建议对我的实施进行任何改进。

最好的，

于 2012-05-15T01:40:34.867 回答
1

最大值比中值容易得多

在Python中，如果数字列表是L，就这么简单

L.count(max(L))

L.count 是 O(n)
max(L) 也是 O(n)

这个简单的解决方案确实会检查每个元素两次，但算法总体上仍然是 O(n)

于 2012-05-14T06:58:41.483 回答
0

我认为这也可以：

O(n) 算法

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
于 2012-05-14T06:53:01.163 回答