這題目的邏輯是找出陣列中出現次數過半的元素,這裡有使用一層 for 迴圈遍歷整個陣列後,用 HashMap 來操作存儲查找,Map 時間可以視為常數時間,時間複雜度可以達到 O(n)
,這裡有 JAVA 和 Python 的寫法。
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
給定一個陣列 nums 大小為 n,回傳這個出現多次的元素。
這個出現多次的元素,出現超過半數。你可以認為這個出現多次的元素總是在這個陣列裡。
題目連結:https://leetcode.com/problems/majority-element/
n == nums.length
1 <= n <= 5 * 104
109 <= nums[i] <= 109
Input: nums = [3,2,3]
Output: 3
Input: nums = [2,2,1,1,1,2,2]
Output: 2
- 遍歷陣列裡所有的元素
- 把元素和次數存在 Map 裡 ( key:value )
- 當下已有的元素,把 key 的次數 ( value ) +1
- 把 Map 裡次數 (value) 大於陣列一半的 key 回傳
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> isMap = new HashMap<Integer, Integer>();
int ret=0;
// foreach 寫法,類型 int 遍歷後把 nums 裡的每個值丟進 num
for (int num: nums) {
if (!isMap.containsKey(num)) // 如果沒找到指定的 key
isMap.put(num, 1); // (key:value) 添加進 map
else
isMap.put(num, isMap.get(num)+1); // 找到指定的 key 的 value 後 +1
if (isMap.get(num)>nums.length/2) { // 如果當下的 key 的 value 大於陣列長度的一半
ret = num;
break;
}
}
return ret;
}
}
筆者還在學習中,參考了在討論區裡網友一致認同的超簡單解法。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums); // 重新排序 (小到大)
return nums[nums.length / 2]; // 因重新排序後,獲取陣列中間的元素,一定是超過半數的元素
}
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dic = {} # 空字典
# 字典裡找尋 key (索引n),如果找不到 key 的話,把陣列裡的索引 n 添加進字典當 key
# 把次數 0+1 添加進去當 value
for n in nums:
dic[n] = dic.get(n, 0) + 1 # {索引n:0+1}
if dic[n] > len(nums)//2: # 判斷當前的 key 的值,有無大於陣列的一半
return n # 回傳當前的 key
Language | Runtime | Memory |
---|---|---|
Java | 20 ms | 48.5MB |
Python | 131 ms | 14.9MB |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/04/23/LeetCode-169-Majority-Element-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論