您的位置 首页 java

LeetCode基础算法题第81篇:求一个数组里的众数

LeetCode 169. 求众数(Majority Element)

问题描述:

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

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

示例:

C语言实现:

我们很容易想到一种思路:对nums进行排序,排序完的数组nums[len(nums)/2]一定是众数。

这种方法简单直接,算法的复杂度是O(nlogn)。在此不提供代码了,大家可以自己写写。我们这里说一说另一种方法。

首先定义一个变量cur保存出现次数最多的那个数,我们假设数组第一个数是出现次数最多的,且将其计数为1。然后从数组的第二个数开始,如果它和cur相等,那么计数加1,如果不等计数减一,如果计数等于0的时候,说明到目前为止不等于cur的数和等于cur的数数量一样多。那么这个时候cur可能就不是众数,我们要从新开始,按照前面的方法,选择下一个数作为cur,并计数1。如此这般,最后cur保存的就是我们要找的众数。

代码如下:

注意第6行,不会发生数组越界的问题,因为按照题目,众数一定是存在的,所以这里不会越界。

第9行做了一个优化,针对于众数集中出现在数组左边的情况。

python语言的实现:

python推荐用第一种思路来解题,有两个好处:第一,代码简洁,只要一行;第二,sorted和len函数都是内置函数,是C语言实现的,通常效率要比纯python的高的多。

Java语言的实现:

Java的实现和C语言的实现相同。

代码如下:

文章来源:智云一二三科技

文章标题:LeetCode基础算法题第81篇:求一个数组里的众数

文章地址:https://www.zhihuclub.com/191303.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图