在O（N）

Question

假設我有一個這樣的陣列查找下一次出現的每個元素在陣列：[ 1, 2, 3, 4, 5, 6, 1]

我想獲得像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)); 
    } 
} 

即使算法就足夠了。我不需要代碼。

Answer 1

不可能在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

Answer 2

使用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) 

Answer 3

如果我沒有弄錯，如果你想元素或獲得數組中發生的元素超過一個。你可以這樣做。

該解決方案將是nlogn

1. 排序陣列（升序）
2. 環陣列然後比較
3. 如果A [1] == A [1 + 1]然後list.add （A [1]）;

像這樣 enter image description here