實在是沒想過講解題目會分到四篇文章，但如果一篇寫太多題目也不好，這篇是Arrays 101 Explore Card 最後結論章節的三道題目，前兩道題目輕輕鬆鬆解完，第三道則是目前Arrays 101 裡面最難的題目...
這題目一開始就給了一個情境，各位小學升旗應該都有排過隊伍吧？題目就是假設有間學校要幫全體學生拍張照片，學生要按照身高排列...但情境有講跟沒講差不多，就是要解題啊
Input 是一個整數陣列，陣列長度介於1至100之間，陣列內元素大小介於1至100之間
Output 有幾個元素的位置與排序後的陣列不相符
Example 1:
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
heights: [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.
Example 2:
Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights: [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.
Example 3:
Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights: [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.
這題原先思路是想用原地操作，判斷排序時交換幾次，看這樣能不能解出答案，但測試過後是不行...
最終直接使用暴力解，複製Input 的元素到新的陣列，然後排序新的陣列，最後兩個陣列進行比較...
結果傻爆眼，其他人都是用同樣的思路解這題，只是他們排序是用Arrays.sort() 方法去做，我是自己手刻。
Runtime: 2 ms
Memory Usage: 39.9 MB
class Solution {
public int heightChecker(int[] heights) {
int len = heights.length, i = 0;
int[] expected = new int[len];
for (i = 0; i < len; i++) {
expected[i] = heights[i];
}
int temp = 0;
for (i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (expected[j] < expected[i]) {
temp = expected[i];
expected[i] = expected[j];
expected[j] = temp;
}
}
}
int counter = 0;
for (i = 0; i < len; i++) {
if (expected[i] != heights[i]) counter++;
}
return counter;
}
}
這題就有點意思了，一樣會給一個整數陣列，然後要找出第三大的整數。
Input 是一個整數陣列，陣列長度介於1至10^4之間，陣列內元素大小介於-2^31至2^31-1之間
Output 有幾個元素的位置與排序後的陣列不相符
Example 1:
Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.
Example 2:
Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.
這題解法直覺上就是要記錄前三大的元素，跑一次迴圈就能得到結果了，不過實際上要寫出來會多很多判斷。
Runtime: 1 ms
Memory Usage: 43.3 MB
class Solution {
public int thirdMax(int[] nums) {
int len = nums.length;
if (len == 1) return nums[0];
if (len == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
int[] rank = new int[] {-1, -1, -1};
for (int i = 0; i < len; i++) {
if (rank[0] == -1) {
rank[0] = i;
continue;
}
int num = nums[i];
if (rank[1] == -1) {
if (nums[0] > num) {
rank[1] = i;
}
else if (num > nums[0]) {
rank[1] = rank[0];
rank[0] = i;
}
continue;
}
if (rank[2] == -1) {
if (num > nums[rank[0]]) {
rank[2] = rank[1];
rank[1] = rank[0];
rank[0] = i;
} else if (num > nums[rank[1]] && num != nums[rank[0]]) {
rank[2] = rank[1];
rank[1] = i;
} else if (num < nums[rank[1]]) {
rank[2] = i;
}
continue;
}
if (num > nums[rank[0]]) {
rank[2] = rank[1];
rank[1] = rank[0];
rank[0] = i;
} else if (num > nums[rank[1]] && num != nums[rank[0]]) {
rank[2] = rank[1];
rank[1] = i;
} else if (num > nums[rank[2]] && num != nums[rank[0]] && num != nums[rank[1]]) {
rank[2] = i;
}
}
return rank[2] == -1 ? nums[rank[0]] : nums[rank[2]];
}
}
這題就是Arrays 101 裡面最難的題目了，題目一樣是會給一個整數陣列，陣列長度為n的話，陣列內元素大小就是1到n之間，但中間會有缺幾個元素，會以重複的元素出現，我們要找出缺哪幾個元素。
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Example 2:
Input: nums = [1,1]
Output: [2]
這題我沒有解出來，原本是有用暴力解法，建立一個ArrayList，然後第一個回圈把1~n放進去ArrayList，再來第二個迴圈把出現的元素從ArrayList 中刪除，最後就是有缺的元素了，只不過這方法在某個測項中time out 了。
正式的解法可以參考這篇[Day 21] 演算法刷題 LeetCode 448. Find All Numbers Disappeared in an Array (Easy)
她的解法最後分數為：
Runtime: 308 ms
Memory Usage: 42.6 MB
結束了漫長的Arrays 101 篇章，沒想到最後一題是要利用負號標記的已經看過的索引值啊...
雖然看到的第一個想法是，同樣都是跑兩次迴圈，為什麼他的可以過我的不行，不過後來想到ArrayList 要刪除中間元素的話效率本來就比較慢，所以跑到time out 也是正常，而且他的方法也確實好很多，真是上了一課，真的要多動腦啊！
iThome鐵人賽
看影片追技術