資料結構與算法——數組數組

題型1：如何用遞歸實作數組求和

方法1：

題型2：如何用一個for循環列印一個二維數組

方法1：array在二維數組中的行号和列号分别為[i/MAXY]，[i%MAXY]

題型3：用遞歸和非遞歸的方法實作二分查找

題型4：如何在排序數組中，找出給定數字出現的次數

方法1：二分查找，分别找出左邊界和右邊界，左右邊界的差

方法2：順序查找，統計計數

題型5：如何計算兩個有序整型數組的交集

方法1：采用二路歸并來周遊兩個數組，分别用i、j從頭開始周遊兩個數組，如果arr[i]<arr[j]，i++；如果arr[i]>arr[j],j++；否則将arr[i]存放到交集中,i++,j++;

方法2：順序周遊兩個數組，将數組元素存放到哈希表中，同時統計的數組元素進行計數。如果為2，則為兩者的交集元素

方法3：周遊兩個數組中任意一個數組，将周遊得到的元素放到哈希表，然後周遊另外一個數組，同時對建立的哈希表進行查詢，如果存在，則為交集元素

題型6：如何找到數組中重複次數最多的數

方法1：以空間換時間，可以定義一個數組int count[MAX],并将其數組元素都初始化為0，然後周遊數組，對count[A[i]]++操作，在count中找出最大的數。

方法2：使用map映射表，通過引入map表，其中第一為關鍵字，第二個為關鍵字出現的次數，然後判斷次數大小。

題型7：如何在O(n)的時間複雜度内找到數組中出現次數超過了一半的數

方法1：hash法，首先建立一個hash_map，其中key為數組元素值，value為此數出現的次數。周遊一遍數組，用hash_map統計每個數出現的次數。

方法2：partition法，由于出現次數最多的元素肯定也會是中位數，是以，每次用patition找到一個數的位置，如果該數剛好為中位數，則就是超過了一半的數。

方法3：每次取出兩個不同的數，剩下的數字中重複出現的數字肯定比其他數字多，将規模縮小化。如果每次都删除兩個不同的數，那麼剩下的數字裡，原頻度最高的數出現的頻率一樣超過了50%。

題型8：如何找到數組中唯一的重複元素（數組a[N]，1至N-1個數存放在a[N]中，其中某個數重複一次）

方法1：由于題目要求每個元素隻通路一次，不用輔助存儲空間，可以從原理上入手，采用數學求和法，因為隻有一個數字重複一次，而數又是連續的，根據累加原理，對數組的所有項求和，然後減去1至N-1的和，即為所求的重複數。

方法2：采用異或的方法，相同的數為0，不相同的數為1.

方法3：位圖法，首先申請一個長度為N-1且均為‘0’組成的字元串，然後從頭開始周遊數組a[N]，取每個數組元素a[i]的值，将其對應的字元串中的相應位置置為1，如果已經置過1，那麼該數就是重複的數。

題型9：如果判斷一個數組中的數值是否連續相鄰

一個整數數列，元素取值可能是0～65535中的任意一個數，相同元素不會重複出現；0是個例外，可以反複出現。如果最大值和最小值的差距大于0的個數，那麼就是不連續的。（如果數組中的元素有重複的，則需要順序求看是否有重複元素以及間隔）

題型10：如何找出數組中出現奇數次的元素

方法1：使用異或的方法，将所有元素進行異或最後剩下的将是出現奇數次的元素

引申：由n個元素組成的數組，n-2個數出現了偶數此，兩個數出現了奇數次（這兩個數不相等），如何用O(1)的空間複雜度，找出這兩個數？

将所有數異或之後，結果相當于将不相等的兩個數a和b異或。x=a^b，求出x中最低位為1，其中肯定a和b中有一個數的該位是為1的，對數組中所有該位為1的數進行異或，所有該位為0的數進行異或。将能分别得到這兩個數。

題型11：如何找出數列中符号條件的數對的個數

方法1：蠻力法，求所有可能的數對的和，看其和是否為該數

方法2：先對數組進行排序，然後使用二分查找方法，用兩個訓示器分别指向第一個和最後一個元素，然後從兩端同時向中間周遊，直到兩個指針交叉。

方法3：用計數排序，将1～N個數放在一塊很大的空間裡面，比如1放在1号位，N放在N号位，O(N)的時間複雜度，然後取值。

引申：如果是任意數組而不是有規律的數組，如何求解數組對？即給定一個任意整數數組array[n]，尋找數組中和值為SUM的數對。

方法1：蠻力法

方法2：同上面的方法2

方法3：将數組hash到hash表，然後在hash表中查找SUM-m

引申：已知大小分别為m、n的兩個無序數組A、B和一個數常數c，求滿足A[i]+B[j]=c的所有A[i]和B[j]

方法1：枚舉法

方法2：排序+二分查找法

方法3：排序+線性掃描法

方法4：map，将一個數組存放到map中，周遊另一個數組，對于數m，在map中查找SUM-m

題型12：如何尋找數列中缺失的數

給一個由n-1個整數組成的未排序的序列，其元素都是1～n中的不同的整數。如何尋找序列中缺失的整數

可以通過累加求和。首先将該n-1個整數詳解，得到sum，然後用(1+n)n/2減去sum，得到的差即為缺失的整數。

題型13：如何判定數組是否存在重複元素（假設數組a有n個元素，元素取值範圍是1～n，如何判定數組是否存在重複元素）

方法1：對數組進行排序，然後比較相鄰的元素是否相同。時間複雜度O(nlogn)

方法2：使用bitmap方法，定義長度為N/8的char數組，每個bit表示對數字是否出現過。周遊數組，使用bitmap對數字是否出現進行統計。時間複雜度O(n),空間複雜度O(n)

方法3：周遊數組，假設第i個位置的數字是A[i]，并且i!=A[i]，則将A[i]交換到下标為A[i]的位置，如果下标為A[i]的位置已經有A[i]==A[A[i]]，則出現重複了。

題型14：如何重新排序數組使數組左邊為奇數，右邊為偶數。

方法1：使用快速排序類似的方法，使用兩個指針分别指向頭和尾，如果不是指向對應的數，則将二者進行交換

題型15：如何把一個整型數組中重複的數字去掉。

方法1：就是周遊數組的每一個元素，将元素與前面的已經周遊過的元素進行逐一比較，如果發現與前面的數組重複，則去掉；如果沒有重複，則繼續周遊下一個元素。由于每一個元素都要與之前所有元素比較，是以時間複雜度為O(n^2)

方法2：将元素進行排序，然後周遊每一個元素，并用count記錄不重複元素的個數，如果目前元素與它前一個元素不相同，執行A[count]=A[i],count++;否則執行下一次循環。

題型16：如何找出一個數組中第二大的數。

方法1：對所有元素進行排序，第二大的數在第二個位置

方法2：用兩個變量分别記錄第一大和第二大的數，對于最大值初始值為首元素，第二大的數初始化為最小的負數。每次用目前元素與最大值比較，如果大于最大值，則将其賦給最大值，将原最大值賦給第二大值，否則如果小于最大值，則與第二大值進行比較。

題型17：如何将數組的後面m個數移動為前面m個數

将前m個元素的順序颠倒；

将後面n-m個元素的順序颠倒

将n個元素的順序全部颠倒

題型18：如何計算出序列的前n項資料

正整數序列Q中的每個元素都至少能被正整數a和b中的一個整除，現給定a和b，如何計算出Q中的前幾項？例如，當a=3，b=5，N=6時，序列3,5,6,9,10,12.可以和歸并聯系起來，給定兩個數組A、B，數組A 存放：3*1,3*2,3*3...數組B存放5*1,5*2,5*3...有兩個指針i、j分别指向A、B的第一個元素，取min(A[i],B[j])并移動較小值的指針，然後繼續比較。

引申：醜數，是隻能包含因子2 3 5的數。