左邊的數字更大

Question

給定一組數字，對於每個數字，打印左邊的第一個數字，它大於當前數字。

例
輸入 - > 5,3,2,4,8,6
輸出 - > -1，5,3,5，-1,8-

O（n）的溶液需要

Answer 1

是的，O（n）算法肯定是可行的。訣竅是使用數字的二進制表示。

我會用你的例子來說明我的算法。假設我們正在處理8位無符號整數（對於32位或64位整數，解決方案基本相同）。

初始化步驟

在初始化步驟中，我們將構建從數字的二進制表示的布爾矩陣。這樣的矩陣顯然可以在O（n）時間內建立。此外，我們將把當前找到的「大於左」的數字及其索引（表格的最底部的行）存儲在名爲「當前更大」的數組中。因此，此陣列中的每個條目都是對(value, index)。它將被初始化爲-1的值（爲簡單起見，索引被跳過;可以說該值是-1, None）。

遞歸步驟

然後，我們需要從頂部掃描這個矩陣底部（最顯著位到最低顯著），由左到右。這將通過功能

biggerNumber(indices, bitNumber) 

其中指數是我們正在處理的索引列表來完成，並位編號對應於我們在看錶的行。這個函數將被遞歸調用。最初的電話是

biggerNumeber([0,1,2,3,4,5], 7) 

由於所有4-7位是零，讓我們考慮掃描位數3.

當從左到右掃描表中，有以下幾種情況：

• 0...0和1...1：在這種情況下，簡直可以說這些數字的較大（需看低位）。

• 10...0：在這種情況下，左邊的數字明顯大於所有正確的數字。因此，對於位數爲0的所有數字，如果此數字的索引大於已存儲在「當前較大」條目中的數字的索引，我們可以使用數字的值更新「當前較大」條目，該數字的位數爲1 （這意味着新找到的號碼比以前找到的鄰居更近）。

因此，對於第3位，我們只能看到10序列中的一個 - 用於索引4和5上。因此，我們更新「當前更大的」索引5（值= 8和該數量的索引爲4，因而對（8,4））

現在，我們需要遞歸。讓我們回顧一下函數簽名：

biggerNumber(indices, bitNumber) 

我們需要打破索引列表分爲兩個：第一個將包括其位在bitNumber位置0和第二將包括那些位爲1這些數字。在我們的例子中，兩個電話是：

biggerNumber([0,1,2,3,5], 2) 
biggerNumber([4], 2) 

這意味着我們現在要看看位數2.自第二個電話是微不足道的，讓我們考慮如何最好應對指數[0,1,2,3,5]：

我們可以看到，即時模式100，所以我們更新「當前做大」爲指標1和2。然後，我們將做進一步的遞歸調用，基於位2的值：

biggerNumber([0,3,5], 1) 
biggerNumber([1,2], 1) 

接下來的兩個步驟是作爲練習留給讀者。通過遵循它你會得到預期的答案。

現在，該算法的複雜性可以評估如下。在每一步我們都將原始數組分成兩部分。所以，每個數字將進入這些數組中的一個。因此，在隨後的遞歸調用中，每個數字將最多分析totalNumberOfBits次。因此，複雜性是totalNumberOfBits*n。

再一次，這個算法不會處理任意長整數。它基於這樣的假設，即我們可以有效地將一個數字轉換爲其二進制表示。但是在大多數現代世界的用例中（當值對應於「票數」，「配置文件視圖」等）時，這是一個有效的假設。

Answer 2

int arr [] = {5，3，2，4，8，6}; 作爲建議的Next Greater Number參考感謝@גלעד-ברקן，我下面的代碼

private void printPrevGreaterElement(int[] arr) { 
    if (arr.length < 1) { 
     return; 
    } 

    Stack<Integer> stack = new Stack<Integer>(); 
    stack.push(arr[0]); 
    int next = arr[0]; 
    int element = 0; 

    System.out.println(next + " -- > " + -1); 

    for (int i = 1; i < arr.length; i++) { 
     next = arr[i]; 

     if (!stack.isEmpty()) { 
      element = stack.pop(); 

      while (next > element) { 
       if (stack.isEmpty()) { 
        break; 
       } 
       element = stack.pop(); 
      } 

      if (element > next) { 
       System.out.println(next + " -- > " + element); 
       stack.push(element); 
      } else { 
       System.out.println(next + " -- > " + -1); 
      } 
     } 
     stack.push(next); 
    } 
} 

Answer 3

def next_great(seq): 
    gsf = seq[0]    # Assign greater_so_far 
    pe = seq[0]    # Record previous element 
    seq[0] = -1 
    for i in range(1, len(seq)): # start from index 1 in array 
     if seq[i] < pe:   # Check if you should exchange it with pe 
      seq[i], pe = pe, seq[i] 
     elif seq[i] < gsf:  # else exchange with gsf 
      seq[i] = gsf 
     elif seq[i] > gsf:  # else update gsf and assign -1 to seq[i] 
      gsf = seq[i] 
      seq[i] = -1 
    return seq