演算法刷題及總結_數組篇拓展
演算法刷題及總結_數組篇拓展
1.劍指 Offer 03. 數組中重複的數字【難度指數：★☆☆】
題目描述
在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的範圍內。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。
示例 1：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
限制：
2 <= n <= 100000
方法一（暴力法）
解題思路
沒什麼好說的，暴力法，雙循環解決。[](￣▽￣)*
程式碼實現
public static boolean duplicate(int[] nums,int[] duplication) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
// duplication為已經定義好的數組，把發現的重複數字存入該數組第一個位置返回即可
if (nums[i] == nums[j]) {
duplication[0] = nums[i];
return true;
}
}
}
return false;
}
演算法分析
由於採用了雙循環依次比較相互之間兩個元素，所以時間複雜度顯而易見為O(n^2)，空間複雜度為O(1)。當然，因為已知2 <= n <= 100000，如果數組是較大量級，則耗費時間太久，所以演算法必須進行優化。
方法二（哈希表）
解題思路
在暴力解法中，我們先遍歷每一個元素，然後再從其餘的元素中查找這個元素是否存在，其實這裡要的就是能高效的判斷一個元素是否已經存在，我們可以使用哈希表，因為哈希表判斷是否存在的時間複雜度是 O(1)。
偽程式碼
- 先初始化一個哈希表 (HashSet)
- 然後遍歷每一個元素，分別對每一個元素做如下的處理：
- 先判斷哈希表中是否存在這個元素；
- 如果存在的話，則說明這個元素重複，則直接返回；
- 否則，將這個元素加入到哈希表中，方便後續的判重。
程式碼實現
public static boolean duplicate(int[] nums,int[] duplication) {
// 初始化一個哈希表
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
// 判斷當前元素是否已經存在
if (set.contains(nums[i])) {
// 如果存在，則直接返回
duplication[0] = nums[i];
return true;
}
// 否則的話，將當前元素放入到哈希表中，方便後續的查找判重
set.add(nums[i]);
}
return false;
}
演算法分析
以上演算法實現的複雜度分析：時間複雜度是 O(n)，空間複雜度是 O(n)。
時間複雜度 O(n)，對於數據規模 10 萬級別的話，運行速度是可以接受的。但是這裡的空間複雜度則變為 O(n)，因為哈希表需要申請額外的 n 個空間，這裡用到的是典型的空間換時間的思想。
方法三（數組代替哈希表）
解題思路
數組代替哈希表。在題目中，有一個資訊，我們需要注意下，那就是數組中每個元素的大小在 0 ~ n – 1 的範圍內。利用這個資訊，我們就可以使用數組代替上面方案二的哈希表，主要的思路見偽程式碼。
偽程式碼
- 定義一個長度為 n 的數組 bucket，然後將所有的元素初始化為 -1
- 在查找處理的時候，使用原數組的元素作為 bucket 的下標，原數組元素對應的下標作為 bucket 的元素值。
程式碼實現
public static boolean duplicate(int[] nums,int[] duplication) {
// 初始化一個數組
int[] bucket = new int[nums.length];
Arrays.fill(bucket, -1);
for (int i = 0; i < nums.length; i++) {
// 判斷當前元素是否已經存在
if (bucket[nums[i]] != -1) {
// 如果存在，則直接返回
duplication[0] = nums[i];
return true;
}
// 否則的話，將當前元素作為索引，當前元素的下標作為值，填入數組中，
// 方便後續的查找判重
bucket[nums[i]] = i;
}
return false;
}
演算法分析
以上演算法實現的複雜度分析：時間複雜度是 O(n)，空間複雜度是 O(n)。
可以看出，時間複雜度和空間複雜度都是和用哈希表的解決方案是一樣的。但是使用數組絕對會有性能的提高，主要表現在如下的兩個方面：
- 哈希表 (HashSet) 底層是使用數組 + 鏈表或者紅黑樹組成的，而且它的數組也是用不滿的，有載入因子的。所以使用數組來代替哈希表，能節省空間；
- 哈希表在判重的時候需要經過哈希計算，還可能存在哈希衝突的情況，而使用數組則可以直接計算得到 index 的記憶體位置，所以使用數組訪問性能更好。
方法四（原地置換）
解題思路
原地置換：對於這種數組元素在 [0, n-1] 範圍內的問題，可以將值為 i 的元素調整到第 i 個位置上進行求解。（此種思想很重要(￣▽￣)／）在調整過程中，如果第 i 位置上已經有一個值為 i 的元素，就可以知道 i 值重複。當然，對於本題變種（需要指出第一個重複出現的數字）就可能會無法通過全部case,因為這個調換元素的過程是隨機的，而且本身數組中元素排列也是隨機的，無法確保選出的數字是第一個出現的數字。
程式碼實現
public static boolean duplicate(int[] nums,int[] duplication) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
// 找出重複元素的判斷條件
if (nums[i] == nums[nums[i]]) {
duplication[0] = nums[i];
return true;
}
// 交換nums[i]和nums[nums[i]]元素位置，再返回while循環條件進行判斷，若nums[i]≠i;繼續循環進行該步驟
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
}
return false;
}
演算法分析
由上面思路不難分析得出，時間複雜度 O(N)，空間複雜度 O(1)。綜上所述，此為最優解法。
值得注意
可能有人會有疑問，nums[nums[i]]這裡，如果nums[i]是一個特別大的數字，不會導致數組越界異常嗎？其實這裡題目做了一個限制，數組元素在 [0, n-1] 範圍內。所以同學們得好好讀題，如果沒有這個限制，確實會出現問題的哦~
2.劍指 Offer 04. 二維數組中的查找 【難度指數：★★☆】
題目描述
在一個 n * m 的二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個高效的函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
示例:
現有矩陣 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
給定 target = 5，返回 true。
給定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
方法一（暴力法）
解題思路
沒什麼好說的，毫無技術含量的暴力法，雙循環解決。[](￣▽￣)*對了，由於本題涉及到二維數組，所以在對m進行賦值時，及求二維數組的列時，必須先判斷二維數組是否為空或者說二維數組的行大於0。
程式碼實現
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0) return false;
int n = matrix[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
演算法分析
以上程式碼的複雜度分析是：時間複雜度是 O(nm)，空間複雜度是 O(1)。繼續優化吧╮(╯▽╰)╭
方法二（二分法）
解題思路
二分法。走火入魔了，這種方法也是本人第一想法。在看到本題描述的數組特性，從左到右是依次遞增的，那麼可以看成是多個排序好的一維數組，所以可以分成多個二分法的小問題。
偽程式碼
- 外層嵌套for循環，將每一列視為單獨排序好的數組進行處理；
- 對matrix矩陣每一列進行二分查找。
程式碼實現
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int n = matrix.length;
int m = 0;
if (n > 0) {
m = matrix[0].length;
}
for (int i = 0; i < n; i++) {
int left = 0;
int right = m - 1;
while (left <= right) {
//為了避免left和right相加之和溢出，採用以下方法
int middle = left + (right - left) / 2;
if (matrix[i][middle] > target) {
right = middle - 1;
}
else if (matrix[i][middle] < target) {
left = middle + 1;
}
else {
//return matrix[i][middle];
return true;
}
}
}
return false;
}
演算法分析
根據以上演算法不難分析，其時間複雜度為O(nlogm),空間複雜度為O(1)。
思維拓展
如果本題所描述的數組為每行從左到右依次遞增，並且每行的第一個整數大於上一行最後一個整數。那麼本題直接可以採用二分法，而且是最優解法。其時間複雜度為O(logn)。因為所有行可以單獨拆分再組合排列成一條從左到右遞增，依次排列的大的一維數組。這不是重點，重點是確定具體的元素與給定的目標元素對比的過程，細節見程式碼。比較巧妙的方法，隨時複習~
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0) return false;
int n = matrix[0].length;
int left = 0;
int right = m * n - 1;
while (left <= right) {
// mid 是一維數組的索引
int mid = left + (right - left) / 2;
// mid / n 是將一維數組的索引轉成二維數組的行坐標
// mid % n 是將一維數組的索引轉成二維數組的列坐標
int midNum = matrix[mid / n][mid % n];
if (midNum == target) {
return true;
} else if (midNum < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
方法三（線性查找）
解題思路
線性查找。 由於給定的二維數組具備每行從左到右遞增以及每列從上到下遞增的特點，當訪問到一個元素時，可以排除數組中的部分元素。從二維數組的右上角或者左下角開始查找。如果當前元素等於目標值，則返回 true。如果當前元素大於目標值，則移到左邊一列。如果當前元素小於目標值，則移到下邊一行。
偽程式碼
-
若數組為空，返回 false
-
初始化行下標為 0，列下標為二維數組的列數減 1
-
重複下列步驟，直到行下標或列下標超出邊界
-
獲得當前下標位置的元素 num
-
如果 num 和 target 相等，返回 true
-
如果 num 大於 target，列下標減 1
-
如果 num 小於 target，行下標加 1
-
-
循環體執行完畢仍未找到元素等於 target ，說明不存在這樣的元素，返回 false。
程式碼實現
public boolean findNumbersIn2DArray(int[][] matrix, int target) {
int m = matrix.length;
if (m <= 0 || matrix == null) {
return false;
}
int n = matrix[0].length;
int i = m - 1;
int j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] < target) {
j++;
}
else if (matrix[i][j] > target) {
i--;
}
else {
return true;
}
}
return false;
}
演算法分析
時間複雜度：O(n+m)。訪問到的下標的行最多增加 n 次，列最多減少 m 次，因此循環體最多執行 n + m 次。
空間複雜度：O(1)。
思維拓展（二叉搜索樹）
其實本題方法三可以以另外一種思路看待，殊途同歸。如下圖所示，我們將矩陣逆時針旋轉 45° ，並將其轉化為圖形式，發現其類似於 二叉搜索樹 ，即對於每個元素，其左分支元素更小、右分支元素更大。因此，通過從 「根節點」 開始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目標值 target 。演算法和程式碼與方法三是一樣的，就不展示了，理解一下思路。
「根節點」 對應的是矩陣的 「左下角」 和 「右上角」 元素，本文稱之為 標誌數 ，以 matrix 中的 左下角元素 為標誌數 flag ，則有:
若 flag > target ，則 target 一定在 flag 所在 行的上方 ，即 flag 所在行可被消去。
若 flag < target ，則 target 一定在 flag 所在 列的右方 ，即 flag 所在列可被消去。
時間複雜度 O(m+n)：其中，n和m分別為矩陣行數和列數，此演算法最多循環 m+n次。
空間複雜度 O(1) : i, j 指針使用常數大小額外空間。
3.劍指 Offer 05. 替換空格 【★☆☆】
題目描述
請實現一個函數，把字元串 s 中的每個空格替換成"%20"。
示例 1：
輸入：s = "We are happy."
輸出："We%20are%20happy."
方法一
解題思路
利用字元串的replace方法。取巧，無意義，掌握方法本身。
程式碼實現
public String replaceSpace(String s) {
return s.replace(" ", "%20") ;
}
方法二（字元數組）
解題思路
由於每次替換從 1 個字元變成 3 個字元，使用字元數組可方便地進行替換。建立字元數組地長度為 s 的長度的 3 倍，這樣可保證字元數組可以容納所有替換後的字元。演算法很簡單，我就不贅述偽程式碼了。
程式碼實現
public String replaceSpace(String s) {
//確保所有字元能夠都轉換成%20的形式，並且存放在大小合適的字元數組裡面
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < s.length(); i++) {
//獲得字元串所有元素
char c = s.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
}
else {
array[size++] = c;
}
}
//重點掌握這個方法，經常用就不會忘
String newStr = new String(array, 0, size);
return newStr;
}
演算法分析
- 時間複雜度：O(n)。遍歷字元串 s一遍。
- 空間複雜度：O(n)。額外創建字元數組，長度為 s 的長度的 3 倍。
方法三（原地修改）
解題思路
利用StringBuffer，即動態字元串數組存儲和改變字元串內容。通過遍歷先找出所有空格，統計數量，為字元串分配合適的空間並隨機分配字元（空格即可）。然後遍歷確保每個空格都被02%替換。
偽程式碼
-
在字元串尾部填充任意字元，使得字元串的長度等於替換之後的長度。因為一個空格要替換成三個字元（%20），所以當遍歷到一個空格時，需要在尾部填充兩個任意字元。
-
令 P1 指向字元串原來的末尾位置，P2 指向字元串現在的末尾位置。P1 和 P2 從後向前遍歷，當 P1 遍歷到一個空格時，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否則就填充上 P1 指向字元的值。從後向前遍是為了在改變 P2 所指向的內容時，不會影響到 P1 遍歷原來字元串的內容。
-
當 P2 遇到 P1 時（P2 <= P1），或者遍歷結束（P1 < 0），退出。
程式碼實現
public String replaceSpace(StringBuffer str) {
int P1 = str.length() - 1;
for (int i = 0; i <= P1; i++)
if (str.charAt(i) == ' ')
str.append(" ");
int P2 = str.length() - 1;
while (P1 >= 0 && P2 > P1) {
char c = str.charAt(P1--);
if (c == ' ') {
str.setCharAt(P2--, '0');
str.setCharAt(P2--, '2');
str.setCharAt(P2--, '%');
} else {
str.setCharAt(P2--, c);
}
}
return str.toString();
}
演算法分析
時間複雜度 O(n)： 遍歷統計、遍歷修改皆使用 O(n)時間。
空間複雜度 O(1) ： 由於是原地擴展 s 長度，因此使用 O(1)額外空間。
值得注意
- Stringbuffer是動態字元串數組
- append()是往動態字元串數組添加，跟「xxxx」+「yyyy」相當那個『+』號
- 跟String不同的是Stringbuffer是放一起的
- String1+String2 和Stringbuffer1.append(「yyyy」)雖然列印效果一樣，但在記憶體中表示卻不一樣
- String1+String2** 存在於不同的兩個地址記憶體
- Stringbuffer1.append(Stringbuffer2)放在一起
4.劍指 Offer 29. 順時針列印矩陣【★☆☆】
題目描述
輸入一個矩陣，按照從外向里以順時針的順序依次列印出每一個數字。
示例 1：
輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]
示例 2：
輸入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出：[1,2,3,4,8,12,11,10,9,5,6,7]
方法（模擬）
解題思路
根據題目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的對應輸出 [1,2,3,6,9,8,7,4,5] 可以發現，順時針列印矩陣的順序是 「從左向右、從上向下、從右向左、從下向上」 循環。因此，考慮設定矩陣的「左、上、右、下」四個邊界，模擬以上矩陣遍歷順序。
偽程式碼
- 空值處理： 當 matrix 為空時，直接返回空列表 [] 即可。
- 初始化： 矩陣 左、右、上、下 四個邊界 left , r ight, top , bottom，用於列印的結果列表arr。
- 循環列印： 「從左向右、從上向下、從右向左、從下向上」 四個方向循環，每個方向列印中做以下三件事 （各方向的具體資訊見下表） ；
- 根據邊界列印，即將元素按順序添加至列表arr尾部；
- 邊界向內收縮1（代表已被列印）；
- 判斷是否列印完畢（邊界是否相遇），若列印完畢則跳出。
- 返回值： 返回arr即可。
程式碼實現
public int[] spiralOrder(int[][] matrix) {
if ( matrix.length == 0 || matrix == null) {
return new int[0];
}
// 分別表示上下左右四個分界
int left = 0;
int top = 0;
int right = matrix[0].length - 1;
int bottom = matrix.length - 1;
int size = 0;
int[] arr = new int[(right + 1) * (bottom + 1)];
while (true) {
// left——>right
for (int i = left; i <= right; i++) {
arr[size++] = matrix[top][i];
}
if (++top > bottom) {
break;
}
// top——>bottom
for (int i = top; i <= bottom; i++) {
arr[size++] = matrix[i][right];
}
if (--right < left) {
break;
}
// right——>left
for (int i = right; i >= left; i--) {
arr[size++] = matrix[bottom][i];
}
if (--bottom < top) {
break;
}
// bottom——>top
for (int i = bottom; i >= top; i--) {
arr[size++] = matrix[i][left];
}
if (++left > right) {
break;
}
}
return arr;
}
演算法分析
時間複雜度 O(MN) ： M, N 分別為矩陣行數和列數。
空間複雜度 O(1)： 四個邊界 left , right , top , bottom使用常數大小的額外空間（arr為必須使用的空間）。
值得注意
本題不涉及很多演算法，但是需要對於邊界界定有一個清晰的認識，這也是模擬過程的關鍵。所以注意i++和++i的區別，並且if判斷語句也是另外一個關鍵點，控制行列。同時前面曾經總結過一個類似的螺旋矩陣，注意兩者之間的區別。綜上，注意小細節問題~
5.劍指 Offer 50. 第一個只出現一次的字元【★☆☆】
題目描述
在字元串 s 中找出第一個只出現一次的字元。如果沒有，返回一個單空格。 s 只包含小寫字母。
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 " "
方法一（哈希表）
解題思路
通過題意可以知道，本題需要統計每個字元的出現次數並且能夠進行遍歷。第一時間應該想到的就是利用哈希表。以字元為key，出現的次數設為value，建立鍵值對，記錄資訊。可以利用containsKey()方法來區別字元出現在次數。如果是首次出現，就將該key對應的value設為true;反之設為false,則表明已經出現過了。在將所有字元的出現資訊記錄完畢之後，從頭遍歷哈希表確認第一個只出現過一次的字元並返回即可。如圖所示。
偽程式碼
-
利用HashMap初始化字典，記為 dic ；
-
遍歷字元串 s 中的每個字元 c，字元統計 ；
-
建立鍵值對關係：
-
若dic中不包含鍵(key)c ：則向dic中添加鍵值對(c, True) ，代表字元c的數量為1；
-
若dic中包含鍵(key)c ：則修改鍵c的鍵值對為(c, False) ，代表字元c的數量>1 。
-
-
查找數量為1的字元：遍歷字元串s中的每個字元c；
-
若dic中鍵c對應的值為True則返回c。
-
返回 ‘ ‘ ，代表字元串中無數量為1的字元。
程式碼實現
public char firstUniqChar(String s) {
HashMap<Character, Boolean> dic = new HashMap<>();
char[] sc = s.toCharArray();
//遍歷字元串數組，建立鍵值對關係
for(char c : sc) {
dic.put(c, !dic.containsKey(c));
}
for(char d : sc) {
//若鍵值對值為True,則說明該字元只出現過一次，即返回該key
if(dic.get(d)) return d;
}
return ' ';
}
演算法分析
時間複雜度 O(n)：n為字元串s的長度；需遍歷s兩輪，使用 O(n)；HashMap查找操作的複雜度為O(1)；
空間複雜度 O(1)：由於題目指出s只包含小寫字母，因此最多有26個不同字元，HashMap存儲需佔用O(26) = O(1)的額外空間。
方法二（整型數組代替哈希表）
解題思路
考慮到要統計的字元範圍有限，也可以使用整型數組代替 HashMap。ASCII 碼只有128個字元，雖然本題只涉及小寫字母，但是為了能夠存儲方便，使用長度為128的整型數組來存儲每個字元出現的次數（因為a對應的ASCII碼為97，後面會表示到z,所以相應的數組也得有這個範圍，不然會出現數組越界異常）。原理同方法一，但是可以學習此種思想。
程式碼實現
public int FirstNotRepeatingChar(String str) {
int[] cnts = new int[128];
for (int i = 0; i < str.length(); i++)
cnts[str.charAt(i)]++;
for (int i = 0; i < str.length(); i++)
if (cnts[str.charAt(i)] == 1)
return i;
return -1;
}
演算法分析
時間複雜度 O(n)：n為字元串s的長度；需遍歷s兩輪，使用 O(n)；
空間複雜度 O(1)：由上文分析，整型數組只需要O(128)的額外輔助空間，即O(1)。
除此之外，這種思想可以拓展到其他題目，比如需要某個字元的精確次數或者字元本身，此方法都可以進行判斷和求解。
方法三（有序哈希表）
解題思路
在哈希表的基礎上，有序哈希表中的鍵值對是按照插入順序排序的。基於此，可通過遍歷有序哈希表，實現搜索首個 「數量為1的字元」。哈希表是去重的，即哈希表中鍵值對數量≤字元串s的長度。因此，相比於方法一，此方法減少了第二輪遍歷的循環次數。當字元串很長（重複字元很多）時，方法三則效率更高。在Java中使用LinkedHashMap實現有序哈希表。
程式碼實現
public char firstUniqChar(String s) {
//初始化
Map<Character, Boolean> dic = new LinkedHashMap<>();
char[] sc = s.toCharArray();
//建立鍵值對關係
for(char c : sc) {
dic.put(c, !dic.containsKey(c));
}
for(Map.Entry<Character, Boolean> d : dic.entrySet()) {
if (d.getValue()) {
return d.getKey();
}
}
return ' ';
}
演算法分析
時間複雜度 O(n)：n為字元串s的長度；需遍歷s一輪，使用 O(n)；
空間複雜度 O(1)：由上文分析，遍歷有序哈希表只需要O(26)的額外輔助空間，即O(1)。
以上均為《劍指offer》中有關數組題目的集中總結，後續數組篇估計會有更新，敬請期待。(๑╹◡╹)ﾉ”””
