陣列中有多少數字小於給定數字？

天真的是O（n）。有沒有一個是O（log n）甚至O（1）？陣列中有多少數字小於給定數字？

排序數組如何？如何使用二叉搜索樹？

我的數組的大小爲n = [2 ^（h + 1）] - 1？ // H =完全二叉樹

來源

2010-04-26 Raihan

它開始看起來很像功課... – mmr 2010-04-26 02:18:56

你只是問？或者你是否親自探索過這個問題？ – abelenky 2010-04-26 02:20:17

實際上看起來像一個面試問題;一個經典。 – 2010-04-26 02:21:16

未分類
的高度如果陣列沒有排序，那麼你可以做的比爲O（n）沒有更好的。證明：假設你沒有看到數組中的每一個元素，那麼攻擊者可能只是使你沒有看到比給定數字更大或更小的元素，使得你的計數不正確。所以，比O（n）好是不可能的。

排序
如果數組進行排序，然後就可以通過定位大於或等於給定數目的第一元件確定的結果在O（log n）的時間，然後簡單地減去該指數從數組的大小。

來源

2010-04-26 02:23:38

@caf如何如此 - 你仍然可以做二進制搜索。 – WhirlWind 2010-04-26 02:40:03

爲了改進Micheal所說的，最好的結果是二分搜索，它將搜索與給定元素相等的元素，然後迭代該數組，直到達到一個大值。 – 2010-04-26 02:56:54

@Grue如果你做二分搜索，你不需要迭代數組。你只需要知道它中的元素的數量。 – 2010-04-26 03:00:02

使用未分類，你不能比O（n）做得更好。最後。

隨着排序，你可以在最壞的情況下使用二進制搜索O（log（n））。現在，假設陣列布局具有像樣的熵，或者通過瞄準期望點（大部分）是線性的，就好像佈局是純線性的那樣，現在你可以改進它。

例如，使用[0] = x，a [n] = y和您的閾值v取代排序數組a [n]，而不是在n/2處平分數組， [n *（vx）/（yx）] 使用常規佈局（a [i] = const1 * i + const2）可以得到O（1）中的結果，一次命中+ - 舍入誤差，所以最差2.使用「白噪聲」隨機佈局（所有值都是相同可能的），你會得到比O（log（n））更快的速度。

來源

2010-04-29 11:52:01

陣列中有多少數字小於給定數字？

回答

相關問題