今天電話面試遇到的問題，大家有什麼帥氣想法嗎？
Q. 假設有100萬筆浮點數的資料"均勻分布"在1~100之間，給定k，要判斷k是否在這些資料中，有什麼好方法？

我提了如果只做一次就用linear search 花 O(n)，要做很多次就排序後每次花O(lg n)
還有一個效率很差的隨機演算法
聽說均勻分布是關鍵，讓我想用hash table，不知是否為最佳解

均勻分布的話用hash table應該可以每次O(1)?

恩恩我也是這麼想，所以你的話也會hash囉

話說我覺得hash真是犯規，就跟counting sort的感覺好像

目前想到最快的就hash，對均勻分布的資料拿空間換時間很有效

了解，謝啦！

每個數字乘 10000 做 bucket sort

哇！是笨廖耶，太感動了寫演算法你就會看XD
以sort來說好像真的很適合！所以就是乘10000之後以整數部分為bucket排序囉，蠻帥的方法，乘數10000為10000的理由是你取 100萬/100 對吧

嗯