版權聲明：本文為苦逼的碼農原創。未經同意禁止任何形式轉載，特别是那些複制粘貼到别的平台的，否則，必定追究。歡迎大家多多轉發，謝謝。
作者：帥地
我們平時在刷題的時候，我覺得大緻可分為以下幾類題
1、這道題的暴力解法很簡單，幾乎人人都會做，但最優解卻很難。
2、如果你懂某些算法思想，這道題很簡單，如果不懂，那麼這道題頓時很難，例如有些需要dp來處理的。
3、這種題型沒做過，沒啥思路，但接觸過好幾道之後，便會覺得異常簡單，例如不能使用加減乘除運算符來完成加法運算。
4、最後一種是屬于真正的難題，思路難想 ，就算知道了思想，編碼也很難，因為臨界點之類的特别多，邏輯特别複雜。
而我今天要強調的就是第一類題，我這裡給的建議是，我們要追求極緻，并且我今天會給出2道例題，大家也可以想想這2道題的解法。如果這2道題你不懂怎麼做，那麼看完一篇文章會有所收獲。
我在牛客網刷題的時候，發現有些題的解法，如果你是采用暴力的話，是異常簡單的，但是每次遇到這種題，我都不會輕易馬上寫代碼，而是苦思一會，看看有沒有優雅的解法。不過我去看很多通過的代碼，發現大部分人的解法都是很普通，幾乎算是暴力法，可能那些人看到這道題的時候心想：我去，又秒殺一道題了，三分鐘撸好了代碼，一次就ac了這道題，心裡滿滿的快感，馬上接着下一題走起。
但是，這種做法我是不支援的，因為這道題如果你草草了事，那麼你沒有任何優勢，因為你這種解法别人也會；而且，做完這道題，你可能沒有任何收獲，估計隻收獲了快感。也就是說，做完這道題，你并沒有收獲到這道題最核心的解法。
是以，我覺得，對于這種題，我們一定要追求極緻，不能“得過且過”。把這道題的精華吸收進來，有些題的精華、技巧，是可以開拓你的思路的，進而影響 你對其他題的解法的。
當然，收獲快感提升下解題的動力也是挺好的，而且最普通的解法對部分人來說也是收獲滿滿的。我這裡隻是一個建議，如果可以，請追求極緻。
下面我舉幾個例子，也算是順便一起來刷幾道題。
案例1：建構乘積數組
題目描述：給定一個數組A[0,1,…,n-1],請建構一個數組B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。
這道題簡單嗎？就算不能使用除法，也是挺簡單的，每次算 B[i]，都全部周遊一下數組，兩個 for 循環就搞定了，時間複雜度是 O(n^2)。
但是，我敢保證，這種做法95%的人都會做，沒有任何優勢。是以我們想想是否有更加優雅的解法，有人說，想不出來怎麼辦？
很簡單，想不出來就看看别人怎麼做，百度搜尋 or 讨論區看答案。看别人的解法，一點也不丢人。
是以對于這道題，更好的解法應該是這樣的：
1、先算出 B[i] = A[0] * …A[i-1]。
2、接着算 B[i] = A[i+1]…A[n-1] * B[i](B[i]是步驟1 算出來的值)
代碼如下
public int[] multiply(int[] A) {
int len = A.length;
int[] B = new int[len];
B[0] = 1;
//分兩步求解,先求 B[i] = A[0]*..A[i-1];
for(int i = 1; i < len; i++){
B[i] = B[i-1] * A[i-1];
}
//再求B[i]=A[i+1]*...A[n-1];
int tmp = A[len-1];
for(int i = len - 2; i >= 0; i--){
B[i] *= tmp;
tmp *= A[i];
}
return B;
}
時間複雜度是 O(n)。有人可能會問，那我怎麼知道這個解法是否就為最優解了呢？我覺得這個可以自己判斷，加上多看一些點贊高的人的解法，如果時間複雜度、空間複雜度都和你差不多，那麼幾乎就可以認為是最優解了。就算實際上不是，而大佬們也都這樣解，那麼也可以姑且認為是最優解了。最重要的是，比你最開始想的解法好多了就行了。
案例2：數組中重複的數字
題目描述：在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。數組中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼2和3就是重複的數字了，那麼可以随意傳回2或者傳回3都可以了，任意選擇一個即可。
解法
這道題簡單嗎？如果隻是想 ac 過去的話，那麼挺簡單，例如以下兩種解法
1、給數組排序下，然後從左到右周遊，看看有相鄰的數有沒有相等即可。時間複雜度是 O(nlogn)，空間複雜度O(1).
2、用一個哈希表來存放這些數組，把數組元素值作為 key，相同元素的個數作為 value。周遊的過程中，隻要發現某個 key 的 value 超過 1，那麼這個數就是重複的了，直接傳回。時間複雜度是 O(n)，空間複雜度是 O(n)。
這兩種解法相信都不難，也很容易想到，不過請記住，很容易想到的解法大多數時候都不是最優解。那麼有更好的解法嗎？答是有的，更好的解法是時間複雜度是 O(n),空間複雜度是 O(1)。方法如下：
由于數字的範圍是 0-n-1，那麼我們可以這樣做：從左到右周遊數組arr，對于 arr[i]，我們可以把arr[i]放到數組下标為arr[i]的位置上，即arr[arr[i]] = arr[i]。例如 arr[0] = 4，那麼我們就把arr[0]與arr[4]進行交換。假如數組中沒有重複的數，那麼周遊完成後的結果是 arr[i] = i。如果數組有重複的元素，那麼當我們要把 arr[i] 與 arr[arr[i]] 進行交換的時候，會發現 arr[arr[i]] 的值已經為arr[i]了，并且arr[i] != i。
沒看懂？那我做個示範吧，例如數組為 arr = {2, 3, 3, 0}。步驟如下
1、從左到右周遊，此時數組下标i = 0，即arr[i] = 2。把 arr[0] 與 arr[2] 進行交換，交換的結果為 arr = [3, 3, 2, 0}。
2、i = 0,由于 arr[0] = 3，不滿足 arr[i] = i,是以我們的下标還是不能右移，還是得繼續交換。即把 arr[0] 與 arr[3] 進行交換，結果為 arr[0, 3, 2, 3}。
3、i = 0,此時 arr[i] = i。故下标右移，即 令 i = 1。此時 arr[i] = arr[1] = 3。把arr[1] 和 arr[3] 進行交換，但是這時候 arr[3] = 3.即此時出現了 arr[arr[1]] = arr[3]并且 arr[i] != i 的情況，故出現了重複的元素了，直接把 3 傳回，周遊結束。
如果看不懂，多看兩遍就能看懂了，代碼如下：
public int duplicate(int arr[],int length) {
int i = 0;
while(i < length){
if(arr[arr[i]] == arr[i]){
if(arr[i] == i){
i++;
}else{
return arr[i];
}
}else{
int tmp = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = tmp;
}
}
return false;
}