forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchoidabom.ts
More file actions
40 lines (35 loc) ยท 1.14 KB
/
choidabom.ts
File metadata and controls
40 lines (35 loc) ยท 1.14 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
/**
* Runtime: 19ms, Memory: 52.48MB
*
* ์ ๊ทผ
* ์ง๊ด์ ์ผ๋ก ์๊ฐํ์ ๋, 0๋ถํฐ n๊น์ง์ ์ซ์ ์ค์์ ์๋ ์ซ์๋ฅผ ์ฐพ์์ผ ํ๋ค.
* ์์ ํ์์ผ๋ก ์ ๋ ฌํ ๋ฐฐ์ด์์ ์์๋๋ก ๋น๊ตํ๋ฉด์ ์๋ ์ซ์๋ฅผ ์ฐพ์ ์ ์๋ค.
* Time Complexity: O(nlogn)
* Space Complexity: O(n)
*
* Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
*/
function missingNumber(nums: number[]): number {
const numsLen = nums.length;
const sortedNums = nums.sort((a, b) => a - b); // ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
for (let i = 0; i <= numsLen; i++) {
if (i !== sortedNums[i]) {
return i;
}
}
}
/**
* Runtime: 1ms, Memory: 51.96MB
*
* ์ ๊ทผ
* Follow up์ ๋ํ ํด๊ฒฐ ๋ฐฉ๋ฒ
* 0๋ถํฐ n๊น์ง์ ์ซ์์ ํฉ์ ๊ตฌํ ๋ค, ์ฃผ์ด์ง ๋ฐฐ์ด์ ํฉ์ ๋นผ๋ฉด ์๋ ์ซ์๋ฅผ ์ฐพ์ ์ ์๋ค.
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
function missingNumber(nums: number[]): number {
const size = nums.length;
const sum = (size * (size + 1)) / 2;
const accurate = nums.reduce((sum, num) => sum + num, 0);
return sum - accurate;
}