๐ ๋ชฉ์ฐจ
๐ค ๋ฌธ์ : Majority Element | LeetCode 824
๋ฌธ์ : https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/824/
์ฃผ์ด์ง ๋ฐฐ์ด์์ ์ ๋ฐ ์ด์์ ์ฐจ์งํ๋ ์์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค.
๋จ, Could you solve the problem in linear time and in O(1) space?
๐ก ํ์ด
1. Majoirity Component๋ ๋ค๋ฅธ ์์ ๋ค ํฉ์น๊ฑฐ๋ณด๋ค ๋ ๋ง์ด ๋์จ๋ค๋ ์ !
๊ทธ๋ฅ dictionary ์ด์ฉํด์ ๊ฐ ์์๋ณ ๋์จ ํ์ countํ๋ ๊ฑธ๋ก๋ ๋์ ํ O(1) space๋ง์ ํด๊ฒฐ์ด ์ ๋์ด discussion์ ๋ดค์ต๋๋ค.. ใ
ํต์ฌ์ Majoirity Component๋ ๋ค๋ฅธ ์์ ๋ค ํฉ์น๊ฑฐ๋ณด๋ค ๋ ๋ง์ด ๋์จ๋ค๋ ์ ์ ๋๋ค.
Majoirty component๊ฐ ๋์ค๋ฉด +1, ๋ค๋ฅธ๊ฒ ๋์ค๋ฉด -1์ ํ๋ฉด ๋ง์ง๋ง์๋ ๋ฌด์กฐ๊ฑด count๊ฐ ์์์ฌ์ผ ํ๋ค๋ ์ ์ด์ฃ .
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate, count = None, 0
for i in nums:
if count == 0 :
candidate = i
count = 1
else:
if i == candidate : count += 1
else: count -= 1
return candidateโ
์๋๋ ์์ input์ ๋๋ค.
input | 2 | 3 | 3 |
candidate | 2 | 2 | 3 |
count | 1 | 0 | 1 |
๋ค๋ฅธ candidate์ผ๋ก ์์ํ๋ค๊ฐ๋ ๊ฒฐ๊ตญ 3์ผ๋ก ์ธํ ๋จ
input | 3 | 2 | 3 | 4 | 3 |
candidate | 3 | 3 | 3 | 3 | 3 |
count | 1 | 0 | 1 | 0 | 1 |
์ค๊ฐ์ ๋ค๋ฅธ element๊ฐ ๋ผ์ด์๋๋ผ๋ ๊ฒฐ๊ตญ 3์ด ๋จ
input | 3 | 4 | 4 | 3 | 3 |
candidate | 3 | 3 | 4 | 4 | 3 |
count | 1 | 0 | 1 | 0 | 1 |
์ค๊ฐ์ candidate์ด ๋ฐ๋์๋ค๊ฐ๋ ๊ฒฐ๊ตญ 3์ผ๋ก ๋์์ด
'์๊ณ ๋ฆฌ์ฆ > LEETCODE' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Longest Increasing Subsequence | LeetCode 810 | Python3 ๐ (0) | 2022.03.18 |
---|---|
Task Scheduler | LeetCode 826 | Python3 ๐ (0) | 2022.03.17 |
Divide Two Integers | LeetCode 820 | Python3 ๐ (0) | 2022.03.15 |
Search a 2D Matrix II | LeetCode 806 | Python3 ๐ (0) | 2022.03.14 |
Search in Rotated Sorted Array | LeetCode 804 | Python3 ๐ (0) | 2022.03.13 |