最近碰到的一道比較有趣的面試題: 構造O(1)復雜度數(shù)組，題目要求如下

設計一個特殊的數(shù)組，要求該數(shù)據(jù)結構以下三種操作的時間復雜度均為O(1)

1. 查詢數(shù)組某個位置的元素

2. 將數(shù)組某個位置的元素修改為指定值

3. 將數(shù)組所有元素修改為指定值

這道題的困難之處在于，如何將第三個操作的復雜度降為O(1),正常來說修改所有元素的值要將操作二進行N次，如果操作二復雜度是O(1),操作三必然是O(N)。

最先想到的辦法是用數(shù)組開頭的第一個元素作為所有元素的代表，修改第一個元素代表著修改了所有元素，如果元素不統(tǒng)一，就將第一個元素置為特殊值。

但隨之引發(fā)的問題是，修改了所有元素為x之后，修改其他的某個元素為y，此時再查詢第三個元素，期望的結果是得到之前將其修改為的x，實際結果只能得到其修改前的值，因此這種想法不成立。

最終的解決辦法是這樣的：

我們依然將數(shù)組開頭的第一個元素作為所有元素的代表，同時，我們維護另一個等長的數(shù)組與這個數(shù)組一一對應，存放每個元素所處的層級（最近一次操作的時間），或者使用對象數(shù)組，每個對象包括元素值和層級兩個變量。

舉個例子，所有元素的層級初始都為0，修改某個位置的元素時，我們將其層級修改為當前最大層級+1，修改所有元素時，我們將數(shù)組第一個元素的層級修改為當前最大層級+1，每次查詢時，要查詢元素都和數(shù)組的第一個元素進行層級比較，輸出層級比較大的元素。

這樣的結果時每個操作都變成了兩個O(1)操作，用額外的操作和空間提高了前兩個操作的復雜度，將第三個操作復雜度降為O(1),符合題目要求。

這個想法的來源是，我們的問題是不知道對所有元素的操作和對單個元素的操作的先后順序，當我們知道了先后順序之后我們很容易知道應該取什么值作為輸出，因此我們就定義一個變量來記錄他們的操作順序。

另外，這個想法還有一點改進，當我們進行了很多次操作之后，層級過大會超過數(shù)據(jù)類型能夠存儲的上限。因此，我們在最大層級為N的時候，進行一次降層。

降層操作時，將數(shù)組的每個元素都跟數(shù)組的第一個元素層級比較，判斷其當前應該存儲的值，進行修改，并將所有元素層級降為0，第一個元素層級降為-1。

降層是一個2N的操作，但是當最大層級為N的時候，我們必然已經進行N次修改操作，花費了2N的時間，即N次修改操作共花費了4N的時間，每個操作的時間復雜度平均為O(1)。

以上。

原文鏈接: https://luospaces.com/posts/%E6%9E%84%E9%80%A0o1%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%95%B0%E7%BB%84