forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathleehyeyun.js
More file actions
84 lines (69 loc) Β· 2.17 KB
/
leehyeyun.js
File metadata and controls
84 lines (69 loc) Β· 2.17 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* @param {number[]} nums
* @return {number}
*/
/*
λ¬Έμ λͺ
: Missing Number (LeetCode 268)
λ¬Έμ μ€λͺ
:
κΈΈμ΄κ° nμΈ λ°°μ΄ numsκ° μ£Όμ΄μ§λ€.
μ΄ λ°°μ΄μλ 0λΆν° nκΉμ§μ μ«μ μ€μμ
μ νν νλλ₯Ό μ μΈν nκ°μ μ«μκ° λ€μ΄ μλ€.
(μ¦, μλλ n+1κ°μ μ«μκ° μμ΄μΌ ν¨)
λͺ©ν:
0λΆν° nκΉμ§μ λ²μ μμμ
λ°°μ΄ numsμ μ‘΄μ¬νμ§ μλ "λ¨ νλμ μ«μ"λ₯Ό μ°Ύμ λ°ννλ€.
μ
λ ₯ 쑰건:
- nums.length == n
- 1 <= n <= 10^4
- nums[i]λ 0 μ΄μ n μ΄νμ μ μ
- nums μμ λͺ¨λ κ°μ μλ‘ λ€λ₯΄λ€ (μ€λ³΅ μμ)
μΆλ ₯:
- nums λ°°μ΄μ μλ μ«μ 1κ°λ₯Ό λ°ν
ν΅μ¬ ν¬μΈνΈ:
- μ μ μνλΌλ©΄ μ«μ λ²μλ [0, n] (μ΄ n+1κ°)
- μ€μ λ°°μ΄μλ nκ°λ§ μ‘΄μ¬ β λ°λμ νλλ λΉ μ Έ μμ
- λ°°μ΄μ μ λ ¬λμ΄ μμ§ μμ
μμ 1:
μ
λ ₯: nums = [3, 0, 1]
ν΄μ:
n = 3
μ μ λ²μ: [0, 1, 2, 3]
λΉ μ§ μ«μ: 2
μΆλ ₯: 2
μμ 2:
μ
λ ₯: nums = [0, 1]
ν΄μ:
n = 2
μ μ λ²μ: [0, 1, 2]
λΉ μ§ μ«μ: 2
μΆλ ₯: 2
μμ 3:
μ
λ ₯: nums = [9,6,4,2,3,5,7,0,1]
ν΄μ:
n = 9
μ μ λ²μ: [0, 1, 2, ..., 9]
λΉ μ§ μ«μ: 8
μΆλ ₯: 8
μΆκ° μꡬμ¬ν (Follow up):
- μκ° λ³΅μ‘λ: O(n)
β λ°°μ΄μ ν λ²λ§ μνν΄μΌ ν¨
- κ³΅κ° λ³΅μ‘λ: O(1)
β μΆκ° λ°°μ΄, ν΄μ맡 λ± μ¬μ© λΆκ°
λ¬Έμ μλ:
- λ¨μ νμμ΄ μλλΌ
"μ 체 λ²μμ μ±μ§"μ μ΄μ©ν΄
λΉ μ§ μ«μλ₯Ό μ°ΎμλΌ μ μλμ§ νμΈ
- μνμ μ¬κ³ λλ λΉνΈ μ°μ°μ μ¬κ³ λ₯Ό μꡬνλ λ¬Έμ
*/
var missingNumber = function(nums) {
const n = nums.length;
const expectedSum = (n * (n + 1)) / 2;
let actualSum = 0;
for (let i = 0; i < n; i++) {
actualSum += nums[i];
}
return expectedSum - actualSum;
};
console.log(missingNumber([3, 0, 1]))
console.log(missingNumber([0, 1]))
console.log(missingNumber([9,6,4,2,3,5,7,0,1]))