今天我们一起挑战leetcode第169题Majority Element!
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.
Example 1:
Input: nums = [3,2,3]
Output: 3Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
今天的题目比较单纯,这题是希望我们把题目给我们的一个整数阵列中,找到某个数是出现最多次的,并回传那个数。而且题目保证出现最多次数的数会出现超过阵列长度的一半。
这题也能透过HashMap的手法,以key存放数字,value存放数字出现个数,加上比对每个数字出现个数,如果超过阵列长度的一半,就回传该数字,以此来达成题目的要求。
以下是python的程序码
class Solution:
def majorityElement(self, nums: List[int]) -> int:
dit = {}
for i in nums: # 数字:出现个数
if i not in dit:
dit[i] = 1
else:
dit[i] += 1
length = len(nums)
for i in dit: # 走访字典,逐一检查
if dit[i] > (length) * 0.5:
return i
以下是C++的程序码,与上面解法不同是,在这段程序码中,在建立字典的同时就持续检查,因此不需要在完成後再走访一次HashMap。
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> dit;
for(int num:nums){
if(++dit[num] > nums.size() / 2) #建立加上检查
return num;
}
return 0;
}
};
https://leetcode.com/problems/majority-element/discuss/51612/C%2B%2B-6-Solutions
<<: DAY2:简介Android Studio与Kotlin
>>: 爬虫怎麽爬 从零开始的爬虫自学 DAY3 开发环境-2 安装Visual Studio Code
敏捷思维 敏捷(agile)是一种思维(mindset),由价值观(values),原则(prin...
iOS工程师面试深入浅出(Objective-C)- NSInterger 与 Int 有什麽不一样...
Youtube教学影片连结:https://bit.ly/2ECHcoQ 这次带大家深度了解二元树...
前言 现在取得资料也差不多了,换换使用bid and ask吧!看看这是什麽新厨具,可以制作出什麽新...
机器学习的种类主要分成四种:监督式学习(Supervised learning)、非监督式学习(Un...