剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

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

分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过数组长度的一半。这种方法的时间复杂度为O(n^2),在面试中,第一反应想到的方法往往不是最佳答案,下面我们来寻求更加高效的方式。

一个数出现的次数如果超过数组长度的一半,那么可以得出以下结论:

1.如果把超过数组长度一半的数整理在一起形成数组b,那么不管把b放在数组的什么位置,数组的中位数一定在b中。

2.个数超过数组长度一半的数最多只有一个。

基于上述两点结论,我们可以首先将数组排序,使得超过数组长度一半的那些数靠在一起,然后取排序后数组的中位数,最后判断该数的长度是否超过数组长度的一半。代码如下:

import offer8.QuickSort;

/**
 * 题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
 * @author 大闲人柴毛毛
 * @date 2016年3月16日
 */
public class CountNumber {

	/**
	 * 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过数组长度的一半。
	 * 这种方法的时间复杂度为O(n^2),在面试中,第一反应想到的方法往往不是最佳答案,下面我们来寻求更加高效的方式。
	 */
	
	/**
	 * 一个数出现的次数如果超过数组长度的一半,那么可以得出以下结论:
	 * 1.如果把超过数组长度一半的数整理在一起形成数组b,那么不管把b放在数组的什么位置,数组的中位数一定在b中。
	 * 2.个数超过数组长度一半的数最多只有一个。
	 * 基于上述两点结论,我们可以首先将数组排序,使得超过数组长度一半的那些数靠在一起,然后取排序后数组的中位数,最后判断该数的长度是否超过数组长度的一半。
	 * 代码如下:
	 */
	
	/**
	 * 获取数组中出现次数超过一半的那个数
	 * @param a 输入的数组
	 * @return 返回出现次数超过一半的那个数(返回-1表示函数出错)
	 */
	public static int countNumber(int[] a){
		//若数组为空
		if(a==null || a.length<=0){
			System.out.println("数组为空!");
			return -1;
		}
		
		//对数组排序
		QuickSort.QuickSort(a);
		
		//获取中位数
		int mid = a[a.length/2];
		
		//计算中位数出现的次数
		int count = 0;
		for(int i=0;i<a.length && a[i]<=mid;i++){
			if(a[i]==mid)
				count++;
		}
		
		//判断中位数出现的次数是否超过数组长度的一半
		if(count>=a.length/2)
			return mid;
		else
			return -1;
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		int[] a = {3,1,3,2,3,2,3,2,2,3,5,3,4,2,3,3};
		System.out.println(countNumber(a));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++ STL之vector容器的基本操作

注意事项: 特别注意任何时候同时使用两个迭代器产生的将会是一个前闭后开的区间(具体见插入和删除的例子) 特别注意begin()指向的是vec中的第0个元素,而e...

2467
来自专栏苦逼的码农

从0打卡leetcode之day 5 ---两个排序数组的中位数

最简单粗暴的就是把这两个数组头尾连接起来,然后重新给他们排序一下,冒泡排序相信你信手拈来,当然,你也可以装逼用快速排序。

1521
来自专栏King_3的技术专栏

leetcode-561-Array Partition I

1857
来自专栏calmound

String to Integer (atoi)

问题:将字符窜转换成数字 分析:感觉题目不难,但是细节很多,容易想不到 1.数字前面有空格 如s=“    123456” 2.数字前出现了不必要或多于的字符导...

2718
来自专栏北京马哥教育

看完这篇,你就知道Python生成器是什么

生成器是 Python 初级开发者最难理解的概念之一,虽被认为是 Python 编程中的高级技能,但在各种项目中可以随处见到生成器的身影,你得不得去理解它、使用...

36212
来自专栏诸葛青云的专栏

一看就会的C语言笔记——指针函数、函数指针、回调函数

//函数返回值必须用同类型的变量来接受,也就是说,指针函数的返回值必须赋值给同类型的指针变量。

1620
来自专栏大前端开发

ES6特性之:参数默认值

作为一个开发者,跟进行业步伐是非常需要的,不能躺在现有的知识和经验温床上做美梦。JavaScript的ES2015标准(即我们说的ES6)在2016年已经被广泛...

784
来自专栏Phoenix的Android之旅

如何用反射突破private方法的限制

反射作为Java的一个提高点,经常作为面试的内容之一。今天介绍一下最基本的反射的使用。 如何用反射来使用Class中的private方法。

892
来自专栏机器学习算法与Python学习

“基数排序”展现Python的优雅与简洁

在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

2895
来自专栏IT可乐

Java数据结构和算法(七)——链表

  前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷。在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且...

2677

扫码关注云+社区