forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmmyeon.ts
More file actions
36 lines (30 loc) ยท 1.01 KB
/
mmyeon.ts
File metadata and controls
36 lines (30 loc) ยท 1.01 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
/**
*
* ์ ๊ทผ ๋ฐฉ๋ฒ :
* - ์ฐ์๋๋ ์ซ์ ์ค ๋น ์ง ์ซ์ ์ฐพ๋ ๊ฑฐ๋๊น ๋ฐฐ์ด ์ธ๋ฑ์ค๋ฅผ ํ์ฉํ์.
* - ๋ฐฐ์ด ์์ ์ํํ๋ฉด์ map์ ์์๋ฅผ ํค๋ก ๋ฃ๊ณ , nums ๊ธธ์ด๋งํผ ์ํํ๋ฉด์ map์ ๊ฐ ์๋์ง ์ฒดํฌ
* - ์์ผ๋ฉด ํด๋น ์ธ๋ฑ์ค ๋ฆฌํดํ๊ณ , ์ํ ๋๋๋ฉด nums ๊ธธ์ด ๋ฆฌํด
*
* ์๊ฐ๋ณต์ก๋ : O(n)
* - nums ๊ธธ์ด๋งํผ map์ ์์ ๋ฃ๊ณ , map์ ์์ ์๋์ง ์ฒดํฌํ๋๊น O(n)
*
* ๊ณต๊ฐ๋ณต์ก๋ : O(n)
* - map์ nums ๊ธธ์ด๋งํผ ์ ์ฅํ๋๊น O(n)
*/
function missingNumber(nums: number[]): number {
const set = new Set(nums);
for (let i = 0; i < nums.length; i++) {
if (!set.has(i)) return i;
}
return nums.length;
}
// ๊ณต๊ฐ๋ณต์ก๋ O(1) ๊ฐ์ ๋ฐฉ๋ฒ
// - 0๋ถํฐ n๊น์ง์ ํฉ ๊ตฌํ๊ณ , ์ค์ nums ์์ ๊ฐ ๋นผ์ ๋น ์ง ์ซ์ ๊ตฌํจ
function missingNumber(nums: number[]): number {
let sum = 0;
for (let i = 0; i <= nums.length; i++) {
sum += i;
if (i < nums.length) sum -= nums[i];
}
return sum;
}