從數組中找到給定元素的前輩

如何從給定的數字數組中找到給定數字的前輩？例如，如果給定數組包含 -2,1,0,3
且輸入數字爲0，則前者爲-2。從數組中找到給定元素的前輩

我寫以下代碼：

public static int getPredecessor(int[] inpArr, int key) { 
    int minDiff = key<=0 ? (key-inpArr[0]) : key; 
    int predecessor = key; 
    for(int i=0;i<inpArr.length;i++) { 
     if(inpArr[i] < key && (key - inpArr[i])<=minDiff) 
     { 
      minDiff = key - inpArr[i]; 
      predecessor = inpArr[i]; 
     } 
    } 
    return predecessor; 
}

我所做基本上保持跟蹤所提供的數字和所述陣列中的每個數之間的最小差值的;每遇到最小差異，數組中的該特定數字就被存儲爲前一個數字。如果最終返回語句將返回與輸入數字相同的數字，那麼這意味着在給定數組中沒有找到前驅數據。

我的問題是：
可以以任何方式對代碼進行優化嗎？它運行在O（n）時間和O（1）空間的複雜度上。

來源

2013-02-15 codewarrior

如果數組排序，則可以比O（n）做得更好。 – jtahlborn 2013-02-15 02:23:16

@Dave nope，他在談論價值。排序前的第一個值是哪個值。 – 2013-02-15 02:25:02

啊，我明白了...... – 2013-02-15 02:25:41

上面的代碼不適用於inpArr = [ - 5，-2]和key = -4，inpArr = [ - 5，-2，-3]，key = + 1的情況。所以糾正了它。這是更正後的代碼。

public static int getPredecessorv2(int[] inpArr, int key) { 
    int minDiff = Math.abs(key); 
    int pred = key; 
    if(inpArr[0] < key) { 
     minDiff = key - inpArr[0]; 
     pred = inpArr[0]; 
    } 
    for(int i=0;i<inpArr.length;i++) { 
     if(inpArr[i] < key && (key - inpArr[i])<=minDiff) 
     { 
      minDiff = key - inpArr[i]; 
      pred = inpArr[i]; 
     } 
    } 
    return pred; 
}

來源

2013-02-23 20:38:05 codewarrior

對於未排序數組上的單個查詢（如示例數組所示），O（N）時間是可以實現的最好時間，因爲必須與數組中的每個元素進行比較。

首先對陣列進行排序會花費O（N log N）時間，但是如果預計陣列上有許多查詢，則可以在O（log N）時間內通過二進制搜索完成每個查詢。因此，如果有足夠的查詢，查詢的平均成本可能會低於O（N）。或者，如果希望許多查詢使用相同的小（ish）組鍵值，則使用例如哈希表記錄每個鍵的結果最終將提供平均O（1）性能每個查詢以O（N）空間爲代價。

來源

2013-02-15 02:38:01 Simon

這非常有見地。謝謝！ – codewarrior 2013-02-15 02:51:19

從數組中找到給定元素的前輩

回答

相關問題