數據結構相關。查找大於或等於給定輸入的所有數組元素

我有一個長序列的訂單數量，1000,3000,50000,1000000等。數據結構相關。查找大於或等於給定輸入的所有數組元素

我想查找所有訂單數量超過100000。

簡單的解決方案可通過完整列表可重複和比較，並把匹配上到另一個列表，它會給你所有，其量> 100000

我們是否有任何其他數據結構或者算法的做法，可以更快地解決這個問題？

無序的輸入元素序列。

來源

2015-06-18 AngryJS

您能否展示您目前的嘗試？ –

想到的方法可能是保留訂單的有序列表並執行限制數量的二分查找。在有序列表中該點之前的所有訂單將小於限制數量。

// Generate a random array of numbers 
Random r = new Random(); 
Integer[] numbers = new Integer[r.nextInt(100) + 20]; 
for (int i = 0; i < numbers.length; i++) { 
    numbers[i] = r.nextInt(50000) + 100; 
} 
// Order the array and print it 
Arrays.sort(numbers); 
System.out.println(Arrays.toString(numbers)); 
// Find the index of the amount limit (10000 in this case) 
int index = Arrays.binarySearch(numbers, 10000); 
// Print the slice of array that is lower than the limit amount 
System.out.println(Arrays.toString(Arrays.copyOfRange(numbers, 0, Math.abs(index) + 1)));

來源

2015-06-18 08:14:57 EmirCalabuch

有很多的數據結構，可以給你喜歡Tree，HashSet ...等一個更好的搜索時間。

但是，如果您總是希望獲得超過100k的訂單，那麼您可以非常輕鬆地擁有2個列表（一個用於訂單< 100k，另一個用於> 100k）。但是這對於搜索量總是不變的情況非常具體，而不是一個通用的解決方案。

來源

2015-06-18 08:19:46 Codebender

搜索量可能會有所不同！什麼都可以在這裏應用？ – AngryJS

這取決於您要重複訂單順序的次數，以及它是否被修改了很多。

如果你只想做一次，簡單地遍歷整個序列並計數。它將比建立任何其他數據結構更快，因爲無論如何您必須遍歷所有訂單。

此外，遍歷一百萬件物品的列表將會非常快，即使您重複執行。你確定你在這裏有性能問題嗎？

來源

2015-06-18 08:22:10 zmbq

數據結構相關。查找大於或等於給定輸入的所有數組元素

回答

相關問題