動態數值數組中的動態閾值確定

Question

我有一個〜1000個對象的數組，這些對象是隨時間推移而發展的浮點值（以無法預先確定的方式;假設它是黑匣子）。在每個固定的時間間隔內，我想要設置一個閾值，將最高值的5-15％分開，使得在任何可以最自然地進行區分的區域進行切割，因爲數據點之間存在最大差距在數組中。

對我來說，實現這種算法的最佳方式是什麼？顯然（我認爲）在每個時間間隔結束時採取的第一步是對數組進行排序，但之後我不確定解決此問題的最有效方法是什麼。我有一種感覺，沒有必要列出排序陣列中感興趣區域中連續數據點之間的所有空白，並且有一種比蠻力更快的方法來解決這個問題，但我不確定這是什麼。有任何想法嗎？

Answer 1

您可以編寫自己的快速排序/選擇例程，該程序不會針對完全位於5％-15％範圍之外的子數組發出遞歸調用。但只有1,000件商品，我不確定這是否值得麻煩。

另一種可能性是使用花哨的數據結構隨着值的變化在線追蹤最大差距（例如，用子樹數（用於快速索引）和最大子樹間隙裝飾的二叉搜索樹）。這絕對不清楚這是否值得麻煩。