面试常备题----数组总结篇(上)
????? 數組是我們程序員最常用的數據結構，也是筆試和面試最喜歡出的題型。要想解決好一道數組題，需要的不僅是扎實的編程基礎，更重要的是，要有清晰的思路，因為數組題經常是一些見都沒有見過的數學題目，需要我們當場分析其中的規律。
????? 考察數組，最主要的是這幾個方面：查找，排序，遞歸和循環，而這往往考察的就是我們編寫高效率代碼的能力。編寫能夠運行的代碼并不難，但要編寫高效的代碼卻是一門需要花時間的功夫，甚至可以說與天賦掛上鉤，有些人天生就是對算法非常敏感，能夠一下子掌握算法的精髓。但事實就是，大部分正在編程的程序員都不具備這種能力，就像我一樣。
????? 所幸，真正的事實就是：大部分人的努力程度并不足以達到與別人拼天賦的程度。
????? 依然是像我一樣，努力的程度實在是太小了！根本沒有資格抱怨自己與別人的智商差異！！
??????所以，像是我一樣的平庸之輩，最好的方法就是老老實實的認清楚自己是個怎樣的人：沒有天賦，始終沒有別人努力，理解能力差。。。然后我們才能決定自己接下來應該怎么辦。
?????不斷積累基礎知識是非常好的方法，幸運的是，很大部分的編程并不需要太高深的編程技巧，只要我們對常見的編程技巧足夠熟悉也能夠完全勝任。
????? 首先我們先從遞歸和循環開始說起，這在解決數組題目中是非常重要的基礎。
題目一：寫一個函數，輸入n,求斐波那契數列的第n項。
??????幾乎所有講解遞歸的課本都會用這道題目。
???? ?斐波那契數列的數學表達式如下：
??????這就是遞歸的典型應用：在函數中調用自身。
????? 數學表達式非常清晰的告訴了我們怎樣編程：?
long long Fibonacci(unsigned n) {if(n <= 0){return 0;}else if(n == 1){return 1;}else{return Fibonacci(n - 1) + Fibonacci(n - 2);} }????? 其中，long long就是int類型的擴展，一般的int占4個字節，范圍是-32768~32767，而long long則是8個字節，范圍是-922337203685775808~922337203685775807，這樣是為了防止溢出，這在一些大數目的遞歸問題中非常重要。參數傳遞使用unsigned也是同樣的道理。
??????可惜的是，那些課本并沒有告訴我們這樣的解法存在非常嚴重的效率問題！
??????我們可以用樹型結構來看一下這個遞歸過程(所有的遞歸問題都可以用樹型結構表示):
????? 這種做法正是用循環來代替遞歸以提高效率。
????? 遞歸并不是可以被濫用的技巧，表面上使用遞歸似乎能讓我們程序員看上去非常睿智，但實際上遞歸是一種低效的做法，因為每次函數調用是有時間和空間的消耗的，需要在內存棧中分配空間以保存參數，返回地址和臨時變量，而且往棧里壓入數據和彈出數據都需要消耗時間，更可怕的是，遞歸會引起調用棧溢出的問題，因為每次進程的棧容量是有限的，當遞歸的層次太多的時候，就會引發問題。
????? 但是，遞歸確實可以讓代碼顯得更加簡潔，所以如果遞歸層級不是太多的情況，優先考慮遞歸。
????? 很多實際的問題都可以看成斐波那契數列的應用，像是這樣的題目：
????? 一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上n級臺階總共有多少種跳法。
????? 這道題目別說是程序題，我們經常在小學或者初中的課本中看過。仔細分析一下，就能發現，當一只青蛙跳上第1級臺階后，剩下的其實就是n - 1階的總跳數；跳上第2階臺階后，剩下的就是n - 2階的總跳數，也就是f(n - 1)和f(n - 2)。
????? 這是數學建模的能力，也是面試者所看重的。當然，我們可能無法一下子建好模，實際的情況就是我們部分程序員的數學素養實在是不高，就像我一樣，對于那些高深的算法，很難一下子理解明白，但也并不是說完全沒有辦法，想想敏捷的開發思想，我們可以從最簡單的測試用例開始：
????? 首先是只有1階的情況:f(1) = 1;
????? 然后是只有2階的情況:f(2) = 2;
????? 接著是只有3階的情況:f(3) =?3 = f(2) + f(1);
????? 最后是只有4階的情況：f(4) =?5 = f(3) + f(2) = f(2) + f(1) + f(2);
????? ...
???? f(n) = f(n - 1) + f(n - 2);
???? ?也許程序員永遠也不會成為數學家，因為我們都沒有受過專業的數學訓練，但是我們必須要有發現規律的洞察力，這樣才能寫出好的代碼，就算一時無法洞察出規律，我們還有一個訣竅：測試用例，我們可以從最簡單的測試用例開始，就像上面一樣，只要一開始我們的代碼能夠通過f(1)的情況就行，然后再想辦法通過f(2)和f(3)，最后就是通過n的情況。這就是測試用力的用處，也是我們程序員最大的法寶，只要想辦法通過當前的測試用例就行。
???? ?數組的排序和查找是非常重要的動作，很多實際的問題都需要用到排序和查找，也因為這樣，排序和查找有很多種實現，它們都有各自的優缺點，但對于程序員，最重要的是快速排序和二分查找，因為使用它們能夠顯著的提高效率，尤其是在一些需要注意效率的題目中，就是變相的提示我們，需要使用到快速排序和二分查找。
????? 實現快速排序的關鍵就是在數組中尋找一個數字，然后把數組分成兩個部分：比該數字小的數字移到數組的左邊，大的數字則移到右邊：
int Partition(int data[], int length, int start, int end) {if(data == NULL || length <= 0 || start < 0 || end >= length){throw new std :: exception("Invalid Parameters!");}int index = RandomInRange(start, end);Swap(&data[index], &data[end]);int small = start - 1;for(index = start; index < end; ++index){if(data[index] < data[end]){++small;if(small != index){Swap(&data[index], &data[small]);}}++small;Swap(&data[small], &data[end]);return small;} }?????然后我們用遞歸的方法分別對每次選中的數字的左右兩邊進行排序：
void QuickSort(int data[], int length, int start, int end) {if(start == end){return;}int index = Partition(data, length, start, end);if(index > start){QuickSort(data, length, start, index - 1);}else{QuickSort(data, length, index + 1, end);} }???? 快速排序雖然在總體上的平均效率是最佳的，但并不是任何時候都是最佳的，比如說數組已經排好序，而每輪排序都是以最后一個數字作為比較的標準，快速排序的時間效率就只有O(N * N)。不過一般而言，對于一個n個元素的數組，快速排序的時間復雜度為O(N *?log2N)。
???? 相比其他查找來說，二分查找的比較次數少，查找速度快，平均性能好，但前提是在有序的條件下，所以一般都是先排序，再查找：
????? 我們來看下道題目：
題目二：把一個數組的若干個元素搬到數組的末尾，就是數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。
????? 如果光是看題目，我們一下子不知道到底是怎么回事，就先以一個測試用例開始：假設數組為{1, 2, 3, 4, 5},那么旋轉數組就是{3, 4, 5, 1, 2}，它的最小值就是1。
??? ? 最直觀的做法就是遍歷該數組，然后找出最小值，這樣的時間效率就是0(N)。但如果只是這么簡單的話，就不會用旋轉數組這樣聽都沒有聽過的名詞了。以前高中的時候，數學老師就經常說：要求就是條件。這里也是如此，最好的解決方法就是利用旋轉數組的特點。
??????我們來看一下旋轉數組，就會發現，旋轉數組實質上是以最小值作為分界線將整個數組分為兩個部分，前面部分和后面部分都是大于等于最小值，說明這個數組已經是經過一定程度的排序，在經過排序的數組中查找某個值的最好做法就是使用二分查找，這樣我們就能將時間效率控制到O(log2N)。
?????? 根據題意，兩個遞增數組的分界線就是最小值，我們先得到中間的元素，然后將它與第一個元素和最后一個元素進行比較，如果大于等于第一個元素，說明最小值是在中間元素后面，我們可以指向第二個元素，以此類推，如果中間元素小于等于最后一個元素，說明最小值是在中間元素前面，以此類推。
????? 測試用例并不是一次就足夠，我們還要盡可能的考慮更多的情況：
1.將0個元素放在最小值后面，也就是原來的數組的情況，這時上面的思路就不管用了，因為第一個值就是最小值；
2.考慮這樣的數組{0, 1, 1, 1, 1}，那么{1, 0, 1, 1, 1}就是它的旋轉數組之一，但是我們無法用二分查找找出它的最小值，因為我們無法確定中間那個1到底是在前面的遞增序列還是后面的遞增序列。這時我們就要按照順序來查找了。
??????結合上面的情況，我們可以寫出這樣的代碼：
int Min(int* data, int length) {if(data == NULL || length <= 0){throw new std :: exception("Invalid Parameters!");}int index1 = 0;int index2 = length - 1;int indexMid = index1;while(data[index1] >= data[index2]){if(index2 - index1 == 1){indexMid = index2;break;}indexMid = (index1 + index2) / 2;if(data[index1] == data[index2] && data[indexMid] == data[index1]){return MinInOrder(data, index1, index2);}if(data[indexMid] >= data[index1]){index1 = indexMid;}else if(data[indexMid] <= data[index2]){index2 = indexMid;}}return data[indexMid]; ]int MinInOrder(int* data, int index1, int index2) {int result = data[index1];for(int i = index1 + 1; i <= index2; ++i){if(result > data[i]){result = data[i];}}return result; }????? 當我們拿到一個從未見過的情境的時候，最好的方法就是盡可能的提出不同的測試用例，考察更多的情況，這樣我們就能在不斷通過這些測試的時候完成正確的代碼。讓代碼正確地運行是我們首要的任務，然后才考慮優化的問題，當然，如果一開始就能根據題目的要求聯想到最優解那自然是最好不過了。
??????二分查找體現的是分治策略，而分治策略和遞歸可以說是一對好朋友，像是下面這道題目：
題目三：找出數組中的最大值。
?????這是非常簡單的題目，我們可以使用二分查找結合遞歸：
int GetMax(int* data, int start, int end) {int maxValue;
if(data != NULL && length > 0)
{if(end - start <= 1){if(data[start] >= data[end]){return data[start];}else{return data[end];}}int maxL = GetMax(data, start, start + (end - start) / 2）;int maxR = GetMax(data, start + (end - start) / 2 + 1, end);if(maxL > maxR){maxValue = maxL;}else{maxValue = maxR;}
}return maxValue;
}
???? ?這就是所謂的分治策略。
????? 二分查找是分治策略的一種實現，使用二分查找的條件之一就是我們知道想要找的是一個具體的值。
????? 只要題目中要求我們尋找某個值，也就是一個查找動作，我們都可以考慮使用二分查找，像是查找而快速排序的使用情況更多了，凡是涉及到"快速"這個字眼，我們都可以想想是否可以用快速排序來組織一下數組。
??????二分查找需要經過排序的數組，但如果使用快速排序，就會破壞原來數組的結構，所以我們必須清楚最關鍵的一點：我們是否可以修改數組的結構？
????? 如果上面的題目我們無法修改數組，那么我們就只能使用輔助數組，這也就是所謂的"用空間換取時間"的做法。
??????我們來看下面的這道題目：
題目四：找出數組中出現次數超過數組長度的數字。
??????同樣是從一個測試用例開始：假設數組{1, 2, 3, 2, 2, 2, 5, 4, 2}，那么該數字就是2。
????? 這道題目同樣是從數組中查找某個值，我們的腦海中就會閃過二分查找，因為題目中并沒有說明是排序的，所以我們還得先排序一下，可以利用我們上面的函數Partition：
int MoreThanHalfNum(int* data, int length) {if(CheckInvalidArray(data, length){return 0;}int middle = length / 2;int start = 0;int end = length - 1;int index = Partition(data, length, start, end);while(index != middle){if(index > middle){end = index - 1;index = Partition(data, length, start, end);}else{start = index + 1;index = Partition(data, length, start, end);}}int result = data[middle];if(!CheckMoreThanHalf(data, length, result)){result = 0;}return result; }bool g_bInputInvalid = false;bool CheckInvdlidInArray(int* data, int length) {g_bInputInvalid = false;if(data == NULL || length <= 0){g_bInputInvalid = true;}return g_bInputInvalid; }bool CheckMoreThanHalf(int* data, int length, int number) {int times = 0;for(int i = 0; i < length; ++i){if(data[i] == number){times++;}}bool isMoreThanHalf = true;if(times * 2 <= length){g_bInputInvalid = true;isMoreThanHalf = false;}return isMoreThanHalf; }??????這里我們引入了全局變量g_InvalidInput，原因就是我們有兩種無效輸入情況，而且我們不能像之前那樣只是簡單的拋出異常就行，它們需要作為判斷條件來使用，但是全局變量的使用有個問題，如果其他地方會修改它的狀態，那么我們必須在使用它的時候重新設置它的初始值，以確保我們的代碼能夠擁有正確的前提條件，所以最好的做法就是：除非是返回該值，否則我們應該在測試完該條件后將它設置為初始值。
????? 這樣我們的時間效率就是O(N)，但是我們會修改原來的數組，所以我們必須結合題目的特點想出另一種解法：
int MoreThanHalfNum(int* data, int length) {if(CheckInvalidArray(data, length){return 0;}int result = data[0];int times = 1;for(int i = 1; i< length; ++i){if(times == 0){result = data[i];times = 1;}else if(data[i] == result){times++;}else{times--;}} if(!CheckMoreThanHalf(data, length, result)){result = 0;}return result; }
???? 這樣的解法的思路就是我們知道，要找的數字是數組中出現次數最多的，我們可以在遍歷數組的時候保存兩個值：出現的數字和它出現的次數，如果和它相同，次數加1，如果不相同，次數減一。
?????這種做法就不需要修改原來數組的結構，但也能達到O(N)的結果，也就是以少量的空間換取時間效率的典型做法。
?????在分析數組規律的時候，還有一種方法：動態規劃。
???? 動態規劃是數學分析中求最優解的一種方法，它并不是一種算法，只是幫助我們更快找到規律的一種方法而已，讓我們來看一道題目：
題目五：輸入一個整型數組，既有負數又有正數，數組中一個或連續的多個整數組成一個子數組，求所有子數組的和的最大值，要求時間復制度為O(N)。
???? 這是目前唯一一道指定時間復雜度為O(N)的題目，所以也就要求我們必須有分析算法時間復雜度的能力。
???? 我們還是要從測試用例開始。
???? 我們假設有這樣的數組：{1, -2, 3, 10, -4, 7, 2, -5}，根據題目要求，符合要求的子數組應該是{3, 10, -4, 7, 2}，也就是輸出的和為18。
???? 這樣我們好像也找不到任何規律可言，所以我們就按照直觀的做法來分析一下：
???? 我們從數組的第一個元素開始：
???? {1}:1;
???? {1, -2}:-1,這時我們注意到，累計和為-1，無論下面的元素是什么，累計起來的和也會比下面那個元素小，所以我們選擇拋棄該子數組，重新從下一個元素開始；
???? {3}:3;
???? {3, 10}:13;
?????{3, 10, -4}:9;
???? ...
?????按照這樣的思路，我們可以確定，如果累積和不為負數，我們就可以將該子數組作為最大和子數組的部分，根據這樣的思路，我們可以寫出這樣的代碼：
bool g_InvalidInput = false;int FindGreatestSumOfSubArray(int* data, int length) {if(data == NULL || length <= 0){g_InvalidInput = true;return 0;}g_InvalidInput = false;int curSum = 0;int greatestSum = 0;for(int i = 0; i < length; ++i){if(curSum <= 0){curSum = data[i];}else{curSum += data[i];}if(curSum > greatestSum){greatestSum = curSum;}}return greatestSum; }?????這里引入了一個全局變量，它的作用就是用來標識到底是輸入無效還是子數組的和為0這兩種情況。
???? 如果是使用動態規劃，我們用f(i)來表示以第i個數字結尾的子數組的最大和,然后根據我們上面的思路，可以得出這樣的遞歸公式：
??????就像是求斐波那契數列一樣，我們可以用遞歸來編碼：
bool g_InvalidInput = false;int FindGreatestSumOfSubArray(int* data, int length) {if(data == NULL || length <= 0){g_InvalidInput = true;return 0;}g_InvalidInput = false;int n = length - 1;int curSum = 0;if(n == 0 || data[n - 1] <= 0){curSum = data[n];}else if(n != 0 && data[n - 1] > 0){curSum = data[n] + FindGreatestSumOfSubArray(data, length - 1)；}return curSum; }???? 如果使用循環來代替遞歸，那么代碼就會和上面是一樣的。
???? 動態規劃適用于多階段的決策問題，我們首先要確定問題的決策對象，這里是f(i)，也就是到i為止的子數組的和，然后我們再對決策過程劃分階段，這里每個數組元素都可以視為一個階段，接著再對各階段確定狀態變量，也就是確定條件，最后就是根據狀態變量確定函數表達式和各個階段狀態變量的轉移過程。
???? 但是這種思想有它的局限性，它必須滿足這樣的條件：
1.最優化原理(最優子結構性質)
?????一個最優化策略必須具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，剩下的所有決策必須構成最優策略，也就是說，一個最優化策略的子策略總是最優的。
2.無后效性
?????將各個階段按照一定的次序排列好后，對于某個給定的階段狀態，前面各個階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態，換句話說，每個狀態都是過去歷史的一個完整總結。
???? 因為這是正式的數學方法，所以它非常嚴謹。我們來看一下第一個條件，雖然說得非常復雜，其實也就是一句話：每一步策略都必須確保是最優解，這點在實際的分析中都能達到。最關鍵的是第二個條件，它是確定我們是否能夠使用動態規劃的關鍵條件。無后效性的真正意思就是說，我們在這個狀態采取這個策略，是因為它是當前狀態的最優解，而不取決于過去的決策，像是我們上面在遇到子數組的和為負數的情況下，我們采取的策略就是舍棄過去的子數組的和，而直接從該元素開始，這是當前狀態下的最優解，跟前面到底是舍棄還是直接從當前元素開始的決策沒有任何影響。這就是無后效性。
?????動態規劃的"動態"就是來源于此：我們可以根據當前的狀態動態的更換策略。
?????動態規劃在實現的過程中，為了解決冗余，會采取用空間換取時間的做法，也就是必須存儲該過程中的各種狀態，這也就意味著它的空間復雜度要大于其他做法。這種情況就非常值得我們商榷了，所以我們在面試中必須確定一件事：我們是否可以使用輔助數組。像是上面的代碼，我們已經將空間復雜度控制為O(1)了。
???? 關于上面那道題目的討論并沒有完，如果數組全為負數呢？
???? 上面的代碼對于這種情況的處理就是返回0，但也有可能會要求我們返回最大的負數或者其他情況，這些都需要和面試官商量好。
???? 動態規劃在數組問題中非常常見，像是下面這道題目：
題目六：寫一個時間復雜度盡可能低的程序，求一個數組中最長遞增子序列的長度。
?????我們還是先從一個測試用例開始著手：
?????假設一個數組為{1, -1, 2, -3, 4, -5, 6, 7}，那么它的最長遞增子序列為{1, 2, 4, 6}，那么它的長度就是4。
?????我們來看看這個過程：
?????當i為0時，數組元素為1，所以最長遞增序列為{1};
???? 當i為1時，數組元素為-1 < 1，所以舍棄之前的序列，重新建立序列:{-1};
???? 當i為2時，數組元素為2時，由于2比1，-1都要大，所以現在的遞增序列為{1, 2}, {-1, 2};
???? ...
???? 我們可以看到，它滿足了無后效性，之前我們的策略所建立的序列并不會對我們現在的策略產生影響，所以我們可以利用動態規劃來求解。
?????使用動態規劃，最重要的是要確定各狀態下的函數表達式。假設在目標數組data的前i個元素中，最長遞增子序列的長度為len[i - 1]，那么：
???? len[i] = max{1, len[j] + 1}, 其中，data[i] > data[j],?j <= i - 1。
???? 只要data[i] > data[j]，我們就可以將data[i]附加到前面i - 1個元素產生的遞增子序列后面。
???? 根據這樣的式子，我們可以這樣編碼：
int GetLengthOfSubArray(int* data, int length) {int[] len = new int[length];for(int i = 0; i < length; ++i){length[i] = 1;for(int j = 0; j < i; ++j){if(data[i] > data[j]){length[i] = len[j] + 1;}}}return Max(len); }???? 但是這個代碼的時間復雜度為O(N *?N + N) = O(N * N)，我們還可以進一步優化：
int GetLengthOfSubArray(int* data, int length) {int[] MaxValue = new int[length + 1];MaxValue[1] = data[0];MaxValue[0] = Min(data) - 1;int[] len = new int[length];for(int i = 0; i < length; ++i){len[i] = 1;}int MaxLen = 1;for(int i = 1; i < length; ++i){int j;len[i] = BinarySearch(data[i], MaxValue, 0, i);
if(len[i] > MaxLen){MaxLen = len[i];MaxValue[len[i]] = data[i];}else if(MaxValue[j] < data[i]){MaxValue[j + 1] = data[i];}}return MaxLen; }
????? 現在我們的思路就是找出前面i - 1個元素的最長遞增序列，然后加上第i個元素,由于使用了二分查詢，所以整體的時間復雜度為O(N * log2N)。
??????動態規劃特別適合求子數組這種問題，因為該類問題的最優解都需要用到輔助數組，而且都滿足無后效性。
?????
?????
????
????
????
????
?????
????
?
?????
轉載于:https://www.cnblogs.com/wenjiang/p/3307059.html
總結
以上是生活随笔為你收集整理的面试常备题----数组总结篇(上)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： JAVA WEB开发环境搭建教程
- 下一篇： Android Animation学习（