在O（N）

假设我有一个这样的阵列查找下一次出现的每个元素在阵列：[ 1, 2, 3, 4, 5, 6, 1]在O（N）

我想获得像1 ==输出> 6（对于元件1（0 ^第索引匹配在索引6）

这意味着0 ^第元件下一个匹配是在第六指数发现找到。

如果输入是[4,6,4,6]输出是4 ==> 2和6 = => 3

由于用于4第一匹配索引2（其为四）和第一发现匹配六（2 ^第二元件）在3 ^RD索引

发现如果时间复杂度是O（n ）解决方案非常简单。我试图用O（n）中的代码在栈中找到下一个最好的元素。但我无法找到一种方法来为下一个相同的元素做同样的事情。

import java.util.Scanner; 
import java.util.Stack; 

public class NextGreatestElement { 
    public static void main(String[] args) { 
     int[] inp = {1,4,6,2,39}; 
     Stack<Integer> stack = new Stack<>(); 
     stack.push(inp[0]); 
     for (int i = 1; i < inp.length; i++) { 
      int element = inp[i]; 
      if (element > stack.peek()) { 
       System.out.println(stack.peek() + " ==> " + element); 
       stack.pop(); 
       while (!stack.isEmpty()) { 
        System.out.println(stack.pop() + " ==> " + element); 
       } 
       stack.push(element); 
      } else if (element < stack.peek()) { 
       stack.push(element); 
      } 
     } 
     while (!stack.isEmpty()) System.out.println(stack.pop() + " ==> " + (-1)); 
    } 
}

即使算法就足够了。我不需要代码。

来源

2017-08-10 bharath

是什么'未来最大element'是什么意思？ – Eran

对于这个输入[1,2,3,4,5,6,1]，下一个最大的元素是1，它是2和2，它是3，依此类推，六中没有什么是 – bharath

您可以实现的最佳复杂度是O（nlogn），使用快速排序对数组进行排序，然后遍历它以找到数组中没有更大后继的元素。 –

不可能在O(n)中使用堆栈来实现它。您可以采取HashMap并从右向左迭代保存数字的最后一次出现。它会给你O(n)平均情况下的时间复杂度：

int[] inp = {1, 2, 3, 1, 2, 1, 3}; 
Map<Integer, Integer> h = new HashMap<>(); 
List<Integer> result = new ArrayList<>(); 

for (int i = inp.length - 1; i >= 0; --i) { 
    int cur = inp[i]; 
    int next = -1; 
    if (h.containsKey(cur)) { 
     next = h.get(cur); 
    } 
    h.put(cur, i); 
    result.add(next); 
} 

for (int i = 0; i < inp.length; ++i) { 
    System.out.println("Number " + inp[i] + " next occurence at index " + result.get(inp.length - i - 1)); 
}

可运行版本：http://ideone.com/i6Cx09

来源

2017-08-10 08:08:08 DAle

@bharath，看看这个问题https://stackoverflow.com/questions/4553624/hashmap-get-put-complexity – DAle

-1

使用HashMap或哈希表

横向从右到左，在第一次出现输入值进入收藏

collection_object.put(inp[i], ""+i)

当你下次遇到时只要改变数值就好了

value = collection_object.get(inp[i]) 
v = value.split("==>") 
value = v[0] + "==>" + i 
collection_object.put(inp[i], value)

来源

2017-08-10 09:09:43

我不明白你的答案 – bharath

HashMap collection_object = new HashMap （）; collection_object是一个散列表，在遍历输入数组的时候，当你第一次遇到一个元素时，只要输入这个元素的索引作为key和value，下一次遇到同样的元素。使用第二个代码 –

omg最后，我在阅读完所有评论后明白了你的问题，请在提问时注明。 –

如果我没有弄错，如果你想元素或获得数组中发生的元素超过一个。你可以这样做。

该解决方案将是nlogn

排序阵列（升序）
环阵列然后比较
如果A [1] == A [1 + 1]然后list.add （A [1]）;

像这样 enter image description here

来源

2017-08-10 12:40:14

谢谢你投资你的时间，但这不是我要找的... – bharath

回答

相关问题