官方网站举例,流量型网站,html网页设计简单,深圳网站设计公司费用是给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。 示例 1#xff1a;
输入#xff1a;nums [3,2,3]
输出#xff1a;3
示例 …
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 示例 1
输入nums [3,2,3]
输出3
示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109 进阶尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
方法一如果一个数组有大于一半的数相同那么任意删去两个不同的数字新数组还是会有相同的性质即原来的“多数元素”在删除任意两个不同元素后数组中的“多数元素”的值不变
class Solution(object):def majorityElement(self, nums)::type nums: List[int]:rtype: intlengthlen(nums)#由于一定存在一个长度大于n/2的数k所以用k对应减去不等于k的值后剩余的数的值还是k(eg:2,2,3用一个2对应减去一个3剩余的就是k值2),#初始时随便选择数组中的一个数作为k对数组 进行扫描当遇到的数与选择的数k相同则times1,否则减一当减到零0将遇到的元素作为新的k值knums[0]times0for i in range(0,length,1):#print(i,:)if nums[i]k:times1elif nums[i]!k:times-1if times0:knums[i]times1#print(k)return k
方法二
使用哈希映射HashMap来存储每个元素以及出现的次数。对于哈希映射中的每个键值对键表示一个元素值表示该元素出现的次数。
我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后我们遍历哈希映射中的所有键值对返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法维护最大的值这样省去了最后对哈希映射的遍历。
class Solution(object):def majorityElement(self, nums)::type nums: List[int]:rtype: intvalsnums[0]for i in range(0,len(nums)/21,1):valsnums[i]knums.count(vals)print(vals,:,k)if klen(nums)/2:print(len(nums)/2)breakreturn vals
