正向整数数组，高效实现的想法

我在一个更大的问题中遇到了一个小问题。我有一个正整数数组。我需要在数组中找到一个位置，使得所有小于位置i的元素的数字都应该出现在数组之后。正向整数数组，高效实现的想法

实施例：

（假设阵列在1索引）

2，3，4，1，9,3，2 =>第三POS // 1,2,3都小于4并且在它之后发生。

5，2,1，5 =>第二POS

1,2,1 =>第二POS

1，图4，图6，图7，图2，3 =>不存在

我想使用哈希表，但我不知道具体如何。或者排序会更好？任何想法有效的想法？

来源

2015-09-27 dogacanb

我编辑了这个问题，st =这样，:) – dogacanb

你使用的是特定的语言吗？ –

我将用Python实现。实际上它并不重要，我宁可在一个好的算法之后。 – dogacanb

我们可以通过创建一个地图（或哈希表或其他），它记录了最后一次出现的每一个条目开始：

for i from 1 to n 
    lastOccurrence[arr[i]] = i 
next

我们知道，如果j是一个有效的答案，然后每隔数小于j也是一个有效的答案。所以我们想找到最大的j。最低j明显是1，因为那么左侧子列表是空的。

然后我们可以遍历所有可能的j s并检查它们的有效性。

maxJ = n 
for j from 1 to n 
    if j > maxJ 
     return maxJ 
    if lastOccurrence[arr[j]] == j 
     return j 
    maxJ = min(maxJ, lastOccurrence[arr[j]] - 1) 
next

来源

2015-09-27 14:15:18

感谢尼科，看起来真的很好:)） – dogacanb

关于你的第一个'if'：如果'maxJ'开始为'n'并且根据最后一行只能得到小于它的起始值，那么'j'实际上能够结束更大？ – usr2564301

@Jongware是的，在例子'{2,3,2,2,3}'中。 'j'上升到4，但是'maxJ'是3. –

from sets import Set 
def findMaxIndex(array): 
    lastSet = Set() 
    size = len(array) 
    maxIndex = size 
    for index in range(size-1,-1,-1): 
     if array[index] in lastSet: 
      continue 
     else: 
      lastSet.add(array[index]) 
      maxIndex = index + 1 
    if maxIndex == 1: 
     return 0 # don't exist 
    else: 
     return maxIndex

从最后一个元件的第一，使用set保持已符合元素，如果迭代元素（索引i）不在set，则最大指数是i，并更新set

来源

2015-09-27 14:42:39 Hooting

正向整数数组，高效实现的想法

回答

相关问题