精华内容
下载资源
问答
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入:...
    • 题目描述

    给定一个大小为 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    你可以假设数组是非空的,并且给定的数组总是存在众数。

    • 示例

    示例 1:

    输入: [3,2,3]
    输出: 3
    示例 2:

    输入: [2,2,1,1,1,2,2]
    输出: 2


    • 解决思路一

    既然是假定了一定存在众数,那么我们可以对数组进行排序,排序之后不论是按升序还是降序,众数一定会出现在数组中间的位置。

    • 代码一
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums.sort()
            length = len(nums)
            if length == 0:
                return None
            elif length == 1:
                return nums[0]
            else:
                index = length/2 
                result = nums[index]
                return result
    • 解决思路二

    非常厉害的摩尔投票法

    算法的核心思想是同加,异减。对任意指定的暂定众数,遍历数组中的数字,与该数相同的话,计数值+1,否则计数值-1。如果在某个位置时计数值为0,则表示从数组开始到该位置没有众数。那么就从下一个数字重新开始遍历,以下一个数字作为暂定众数。

    • 代码二
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            #暂定众数为数组的第一个元素
            crowd = nums[0]
            #计数值为1
            count = 1
            #从数组的第二个元素开始遍历
            for i in range(1,len(nums)):
                if nums[i] == crowd:
                    count += 1
                else:
                    count -= 1
                    #如果在某个位置计数值为0 ,就从下一个元素开始重新开始求众数
                    if count == 0:
                        crowd = nums[i+1]
            return crowd
            

     

    展开全文
  • 剑指offer39题:给定一个数组,找出其中出现次数超过1/2len(nums)数字。 leetcode 169. 求众数 https://leetcode-cn.com/problems/majority-element/ 这道题解法非常多,这里主要实现Boyer-Moore 投票算法 ...

    剑指offer39题:给定一个数组,找出其中出现次数超过1/2len(nums)的数字。
    leetcode 169. 求众数 https://leetcode-cn.com/problems/majority-element/

    这道题的解法非常多,这里主要实现Boyer-Moore 投票算法

    本质上, Boyer-Moore 算法就是找 nums 的一个后缀 sufsuf ,其中 suf[0]suf[0] 就是后缀中的众数。我们维护一个计数器,如果遇到一个我们目前的候选众数,就将计数器加一,否则减一。只要计数器等于 0 ,我们就将 nums 中之前访问的数字全部 忘记 ,并把下一个数字当做候选的众数。直观上这个算法不是特别明显为何是对的,我们先看下面这个例子(竖线用来划分每次计数器归零的情况)

    [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

    首先,下标为 0 的 7 被当做众数的第一个候选。在下标为 5 处,计数器会变回0 。所以下标为 6 的 5
    是下一个众数的候选者。由于这个例子中 7 是真正的众数,所以通过忽略掉前面的数字,我们忽略掉了同样多数目的众数和非众数。因此, 7
    仍然是剩下数字中的众数。

    [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

    现在,众数是 5 (在计数器归零的时候我们把候选从 7 变成了 5)。此时,我们的候选者并不是真正的众数,但是我们在 遗忘
    前面的数字的时候,要去掉相同数目的众数和非众数(如果遗忘更多的非众数,会导致计数器变成负数)。

    因此,上面的过程说明了我们可以放心地遗忘前面的数字,并继续求解剩下数字中的众数。最后,总有一个后缀满足计数器是大于 0
    的,此时这个后缀的众数就是整个数组的众数。

    作者:LeetCode
    链接:https://leetcode-cn.com/problems/majority-element/solution/qiu-zhong-shu-by-leetcode-2/

    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            if len(nums) == 1:
                return nums[0]
            target = nums[0]
            freq = 1
            for i in range(1, len(nums)):
                if freq == 0:
                    target = nums[i]
                    freq = 1
                elif nums[i] == target:
                    freq += 1
                else:
                    freq -= 1
            return target
    

    leetcode 229. 求众数 II https://leetcode-cn.com/problems/majority-element-ii/
    这道题是上一道题的升级版,方法还是一样的,主要需要注意出现频率超过三分之一的数字不会多于两个。然后要注意验证所得到数字的频率是否真的超过了三分之一。

    class Solution:
        def majorityElement(self, nums: List[int]) -> List[int]:
            if not nums:
                return []
            if len(nums) == 1:
                return nums
            c1 = c2 = None
            freq_c1 = freq_c2 = 0
            
            for num in nums:
                if num == c1:
                    freq_c1 += 1
                elif num == c2:
                    freq_c2 += 1
                elif freq_c1 == 0:
                    c1 = num
                    freq_c1 = 1
                elif freq_c2 == 0:
                    c2 = num
                    freq_c2 = 1
                else:
                    freq_c1 -= 1
                    freq_c2 -= 1
            valid_c1 = self.check_valid(nums, c1)
            valid_c2 = self.check_valid(nums, c2)
            if valid_c1 == True and valid_c2 == True:
                return [c1, c2]
            elif valid_c1 == False and valid_c2 == True:
                return [c2]
            elif valid_c1 == True and valid_c2 == False:
                return [c1]
            else: 
                return []
            
        def check_valid(self, nums, c):
            freq_c = 0
            for num in nums:
                if num == c:
                    freq_c += 1             
            if freq_c *3 > len(nums):
                return True
            return False
    
    展开全文
  • 数组中一个数字出现次数超过数组长度一半,请找出这个数字。 示例: 输入一个长度为9数组{1,2,3,2,2,2,5,4,2}。 由于数字2在数组中出现了5次,超过数组长度一半,因此输出2。如果不存在则输出0。 解题...

    LeetCode 169.求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
    你可以假设数组是非空的,并且给定的数组总是存在众数。


    解题思路

    摩尔投票法

    核心思路是利用众数的数量优势,用众数去覆盖非众数,剩下来的一定是众数。
    具体步骤为:

    • 从头开始遍历,初始第一个元素为major,遇到相同的,计数器count += 1;
    • 遇到不同的,计数器count -= 1;
    • 计数器为0时,更换major为当前元素。
    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            if not nums: return 
            
            major = nums[0]
            count = 0
            
            for num in nums:
                if count <= 0:
                    major = num
                    count = 1
                elif num == major:
                    count += 1
                else:
                    count -= 1
            
            return major
    

    剑指Offer 39.数组中超过一半的数字

    数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
    示例:

    输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
    由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
    

    解题思路

    摩尔投票法

    剑指这题跟LeetCode基本一样,但这题有诈。
    LC上默认一定存在众数,所以直接返回major即可。
    这题要在遍历一遍,判断major的个数是否大于len(nums)//2。

    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            # write code here
            if not numbers: return 0
            
            major = numbers[0]
            count = 0
            
            for num in numbers:
                if count == 0:
                    major = num
                    count = 1
                elif num == major:
                    count += 1
                else:
                    count -= 1
            
            # 没有后面这段是不对的
            count = 0
            for num in numbers:
                if num == major:
                    count += 1
            
            return major if count > len(numbers)//2 else 0
    

    展开全文
  • Python 实现求众数的三种方法

    千次阅读 2020-07-20 14:34:51
    给定一个长度为 n 的数组,返回众数众数:是指数组出现次数超过 n/2 次元素。 假设数组非空,众数一定存在。 Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2 1:...

     

    给定一个长度为 n 的数组,返回众数。众数:是指数组中出现次数超过 n/2 次的元素。

    假设数组非空,众数一定存在。

    Example 1:
    
    Input: [3,2,3]
    Output: 3
    Example 2:
    
    Input: [2,2,1,1,1,2,2]
    Output: 2

    1:字典,累记数组中出现的各元素的次数,一旦发现超过 n/2 次的元素就返回该元素

    def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums)==1:
                return nums[0]
            numDic = {}
            for i in nums:
                if numDic.has_key(i):
                    numDic[i] += 1
                    if numDic.get(i)>=(len(nums)+1)/2:
                        return i
                else:
                    numDic[i] = 1

    2:利用 list.count() 方法判断(注意 for 循环中如果是访问整个 nums 列表会出现 “超出时间限制” 的错误)

    def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            for i in nums[len(nums)//2:]:
                if nums.count(i)>len(nums)//2:
                    return i

    3:利用sorted(nums)[len(nums)//2]

    def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return sorted(nums)[len(nums)//2]

     

    展开全文
  • Python实现"求众数"三种方法

    万次阅读 2018-09-11 22:23:13
    给定一个长度为n的数组,返回众数众数是指数组出现次数超过n/2次元素 假设数组非空,众数一定存在 Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2 1:字典,累...
  • 【leetcode】Python实现-169.求众数

    千次阅读 2018-06-01 23:58:02
    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 输入: [3,2,3] 输出: 3 输入: [2,2,1,1,1,2,...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: ...
  • 题目:给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 1.方法一遍历:首先想到的方法是将数组的所有元素遍历,计算...
  • 给定一个大小为n的数组,找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: ...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,...
  • 求众数python实现)

    2019-08-29 20:13:35
    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • LeetCode169.python实现: 求众数问题☆

    千次阅读 2019-03-12 14:18:47
    给定一个大小为n的数组,找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1,2,...
  • LeetCode 169. 求众数 Python

    千次阅读 2018-05-31 18:15:23
    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。示例 1:输入: [3,2,3] 输出: 3示例 2:输入: [2,2,1,1,1,2,...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3]输出: 3示例2: 输入: [2,2,1,1,1,2,2]...
  • 题目描述 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。...1.使用一个.set()函数对数组去重,再找到无重复的元素在原来数组中的位置,使用.count()函数 2...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 ...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1...
  • 领扣问题169. 求众数 python解决方案

    千次阅读 2018-12-10 23:58:46
    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: ...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • 求众数

    2019-03-11 23:30:30
    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,...
  • 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1,2,2...

空空如也

空空如也

1 2 3
收藏数 53
精华内容 21
关键字:

python求一个数组中的众数

python 订阅