DAY 24
2
Software Development

[Day 24] 從LeetCode學演算法 - 0229. Majority Element II (Medium)

``````Question:
Given an integer array of size n,
find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
``````
``````Example 1:
Input: [3,2,3]
Output: [3]
``````
``````Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
``````

Java:

``````class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0)
return res;
int n1 = 0, n2 = 1, cnt1 = 0, cnt2 = 0;
for (int num : nums) {
if (num == n1) {
++cnt1;
} else if (num == n2) {
++cnt2;
} else if (cnt1 == 0) {
n1 = num;
cnt1 = 1;
} else if (cnt2 == 0) {
n2 = num;
cnt2 = 1;
} else {
--cnt1;
--cnt2;
}
}
cnt1 = 0;
cnt2 = 0;

for (int num : nums) {
if (num == n1)
++cnt1;
else if (num == n2)
++cnt2;
}

int len = nums.length;
if (cnt1 > len / 3)
if (cnt2 > len / 3)
return res;
}
}
``````

Python的部分，我們這邊除了同於Java的解法以外，

(請留意如果認真按照題目要求的話，這個解法因為會佔用額外O(n)空間

Python:

``````class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
if not nums:
return []
n1, n2, cnt1, cnt2 = 0, 1, 0, 0
for num in nums:
if num == n1:
cnt1 += 1
elif num == n2:
cnt2 += 1
elif cnt1 == 0:
n1 = num
cnt1 = 1
elif cnt2 == 0:
n2 = num
cnt2 = 1
else:
cnt1 -= 1
cnt2 -= 1

cnt1, cnt2 = 0, 0

for num in nums:
if num == n1:
cnt1 += 1
elif num == n2:
cnt2 += 1

res, l = [], len(nums)
if cnt1 > l // 3:
res.append(n1)
if cnt2 > l // 3:
res.append(n2)

return res

'''
# Using Counter but need extra space
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
constraint = len(nums) // 3
count = Counter(nums)
res = []
for k, v in count.items():
if v > constraint:
res.append(k)

return res
'''
``````

「時間/空間複雜度？」
(O(n), O(1)。

0063. Unique Paths II (Medium)

1 則留言

0
t19960804
iT邦新手 5 級 ‧ 2020-10-12 11:02:58

Desolve iT邦新手 5 級 ‧ 2020-10-12 11:38:43 檢舉