马小混

leetcod(002) - 求众数

2019/03/04

求众数

一、题目描述

1、English版本

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

Example 2:

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

2、 中文版

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

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

示例 1:

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

示例 2:

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

二、ruby方案

动态语言和静态语言不同，有很多现有的方法，并不一定非要照着静态的思路或者算法， 相反如果在没有约束的条件下，解决问题才是王道，使用灵活使用动态语言封装的方法是应该首先想到的。

# 剑指offer的思路忘记了，但是ruby本身的特性是应该第一优先级想到的
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
  if nums.empty?
      return nil
  end

  length = nums.size
  nums.each do |num|
    if length < 2 * nums.count(num)
      return num
    end
  end
end

三、python方案

同上

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums is None:
            return None

        for i in nums:
            if nums.count(i) * 2 > len(nums):
                return i

        return None

四、java方案

null

五、经典解法，算法思想

剑指offer 面试题39 数组中超过一半的数 page205

解答之前的注意点

  1. leetcode中是给假设了众数一定存在，如果没有说明，还需要考虑众数是否存在的情况；

  2. 还是优先使用ruby的方法，以解决问题为目的； 但是不是最优的，详见方案一排序方式

方案一： 先排序，在查找

众数m在数组中超过一半，很显然，排序之后中位数一定是众数.

所以，排序之后直接取中位数。

# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
  if nums.empty?
      return nil
  end

  length = nums.size
  nums.sort!
  return nums[length/2]
end

如果是java语言？

对于java语言并没有sort方法，应该使用什么呢？
考虑到效率和本题的特点。
应该使用快排，
1、 随机选一个数字一次快排；
2、 如果排序后当前小于n/2,说明众数大于n/2; 反之亦然； 递归实现快排；
3、 返回中位数；

方案二： 静态语言也简单的解决方案

众数超过n/2, 比其他数的总和还要多，所以提出一个不用排序的方案。

记一个变量m = {数字： 出现次数}

  1. 当连续遇到同一个数字时，次数累加； 否则次数减一；
  2. 次数变为0的时候，将下一个遇到的数据替换当前数字；
  3. 因为众数大于n/2,所以最后剩下的一定是众数。
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
  if nums.empty?
      return nil
  end

  times = 0
  target = 0

  nums.each do |num|
    if times == 0
      target = num
      times = 1
    else
      if target == num
        times += 1
      else
        times -= 1
      end
    end
  end

  target
end


Show Disqus Comments

Post Directory