如何解決涉及傳入的數字或字符流的問題

Question

我遇到了很多面試問題，其中輸入是以輸入數字或字符流的形式。例如： 1.查找輸入數字流的中位數。 2.從輸入流中選擇一個隨機數。

那麼說這是一個傳入流而不是說你有這些數字開頭是什麼意思？

Answer 1

它可能意味着幾件事情：

1. 元素的數量太大，讓他們都在主內存中。你不知道他們有多少人。

2. 每個元素只能處理一次。當我們得到一組數字時，我們可以遍歷它幾次。流不是這種情況。

1.和2.的組合會使問題變得更加困難。有時它使得無法得到確切的答案。例如，找到一個數組的中位數非常簡單。但是，在一般情況下（如果我們無法將它們都保存在主存中，當然是不可能的）在任意數字流中找到確切的中位數。但是，估計它仍然是可能的。再舉一個例子：從流中選擇一個隨機數，以便選擇每個元素的概率是相同的（這裏有一個精確的解決方案，並不明顯）。再次，數組很容易。總之，一個流通常意味着你只能看到每個元素一次，而你不能將它們全部存儲在主內存中，這使得很多問題變得更加困難。