[C#][LeetCode][Easy] 448. Find All Numbers Disappeared in an Array

心得:

題目大意是有一陣列1~N且亂序,必須找出N並找出未出現哪些數字,剛開始我用硬幹的方式,結果顯示Time Out如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class Solution {
public IList<int> FindDisappearedNumbers(int[] nums) {
List<int> ans = new List<int>();

if(nums.Length > 1){
//Sort
for(int i = 0; i < nums.Length; i++){
for(int j = i; j < nums.Length; j++){
if(nums[j] < nums[i]){
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
}
}
}

int n = nums.Length;
for(int i = 0; i < n; i++){
bool b = false;
for(int j = 0; j < nums.Length; j++){
if(i+1 == nums[j]){
b = true;
break;
}
}

if(!b){
ans.Add(i+1);
}
}
}else if(nums.Length == 1){
if(nums[0] != 1){
ans.Add(1);
}
}

return ans;
}
}

後來改用稍為聰明一點的LinQ來找出N,結果還是Time Out如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Solution {
public IList<int> FindDisappearedNumbers(int[] nums) {
List<int> ans = new List<int>();
if(nums.Length > 0){
int max = nums.Max();
if(max < nums.Length){
max = nums.Length;
}
for(int i = 1; i <= max; i++){
if(nums.Any(x=> x == i) == false){
ans.Add(i);
}
}
}

return ans;
}
}

最後生氣了,直接全部都用LinQ,交給RangeExcept直接省略兩個迴圈並且順利解決!

問題:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Solution {
public IList<int> FindDisappearedNumbers(int[] nums) {
List<int> ans = new List<int>();

if(nums.Length > 0){
ans.AddRange(Enumerable
.Range(1, nums.Length > nums.Max() ? nums.Length : nums.Max())
.Except(nums));
}

return ans;
}
}

參考:

  1. [C#] 對List<T>取交集、聯集及差集