๋ฌธ์
ํ์ด ๊ณผ์
์ฃผ์ด์ง ๋ฐฐ์ด์์ ์ค๋ณต๋ ์์๋ฅผ ์ฐพ๋ ๋ฌธ์ ์
๋๋ค.
๋ค๋ง ์๊ฐ ๋ณต์ก๋๊ฐ O(N^2)
๋ณด๋ค ๋ฎ์์ผ ํ๋ฉฐ O(1)
์ ์ถ๊ฐ์ ์ธ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํด์ผํ๋ค๋ ์ ์ฝ ์กฐ๊ฑด์ด ์์ต๋๋ค.
์ฒ์์๋ ๋นํธ ๋ง์คํน
์ ์ด์ฉํด์ ๋ฌธ์ ๋ฅผ ํ๋ ค๊ณ ํ์ง๋ง Javascript
์์ ๋นํธ ์ฐ์ฐ์๋ฅผ ์ฌ์ฉํ ๊ฒฝ์ฐ
ํผ์ฐ์ฐ์๋ฅผ 32๋นํธ๋ก ์ทจ๊ธํ๊ธฐ ๋๋ฌธ์ ์ด๋ฅผ ๋์ด์ค ๊ฒฝ์ฐ overflow
๊ฐ ๋ฐ์ํ์ต๋๋ค.
์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก๋ ์ด๋ถ ํ์
์ด ์์ต๋๋ค.
๋ฐฐ์ด์์ ์ค๋ณต๋ ์์๋ ์ค์ง ํ๋์ด๋ฉฐ ๋๋จธ์ง ์์๋ค์ 1 ~ n
์ ์ซ์๋ค ์ค ํ๋์ ์ซ์์ ๋งค์นญ๋๊ธฐ ๋๋ฌธ์์ด๋ถ ํ์
์ ํ์ฉํด์ ์ค๋ณต๋ ์์๋ฅผ ์ฐพ์์ฃผ๊ธฐ๋ก ํ์ต๋๋ค.
ํน์ ๊ธฐ์ค ๊ฐ pivot
๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ์์์ ๊ฐ์๊ฐ pivot
๋ณด๋ค ํด ๊ฒฝ์ฐpivot
์ดํ์ ์ซ์ ์ค์์ ์ค๋ณต๋ ์์๊ฐ ์กด์ฌํจ์ ์๋ฏธํฉ๋๋ค.
๋ฐ๋ผ์ lo & hi
๊ฐ์ ์ค์ ํด์ฃผ๊ณ ์ด๋ถ ํ์
์ ํตํด ๊ฐ์ ๋ฒ์๋ฅผ ์ขํ๋๊ฐ๋ฉด์
๊ฐ๊ฐ์ pivot
๋ณด๋ค ์์ ์ซ์์ ๊ฐ์๋ฅผ ์ฐพ๋๋ค๋ฉด O(NlogN)
์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์ต๋๋ค.
์ฝ๋
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function (nums) {
let lo = 1;
let hi = nums.length - 1;
let ans = 0;
while (lo <= hi) {
let mid = Math.floor((lo + hi) / 2);
if (count(nums, mid) > mid) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return ans;
};
function count(nums, pivot) {
return nums.filter((e) => e <= pivot).length;
}
'๐ algorithm > leetcode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
LeetCode 739 - Daily Temperatures (Medium) (0) | 2021.03.03 |
---|---|
LeetCode 114 - Flatten Binary Tree to Linked List (Medium) (0) | 2021.03.03 |
LeetCode 347 - Top K Frequent Elements (Medium) (0) | 2021.03.03 |
LeetCode 322 - Coin Change (Medium) (0) | 2021.03.03 |
LeetCode 46 - Permutations (Medium) (0) | 2021.03.03 |
๐ฌ ๋๊ธ