剑指 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 条评论
登录 后参与评论

相关文章

来自专栏编程理解

排序算法(十):基数排序

基数排序也可以称为多关键字排序,同计数排序类似,也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象,对每个对象执行桶排序后,则...

591
来自专栏mwangblog

python条件执行

974
来自专栏技术之路

指针数组和数组指针

指针数组 :就是指针的数组,数组的元素是指针;  数组指针:就是指向数组的指针。 简单举例说明:     int *p1[10];    声明了一个数组,数组的...

1719
来自专栏书山有路勤为径

词语模式_哈希表

已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符 串str中的单词与pattern中的字符一一对应...

674
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

2709
来自专栏程序员互动联盟

【编程基础】c printf知多少

printf()函数是格式输出函数,请求printf()打印变量的指令取决与变量的类型.例如,在打印整数是使用%d符号,在打印字符是用%c 符号.这些符号被称为...

3255
来自专栏编程理解

排序算法(五):堆排序

的时间复杂度即可将二叉树重新调整为有序状态。若构造出一种具有特殊节点顺序的二叉树,使得每次对二叉树执行插入或删除节点操作后,都调整保持二叉树根节点的值为树中节...

441
来自专栏前端知识分享

第179天:javascript中replace使用总结

ECMAScript提供了replace()方法。这个方法接收两个参数,第一个参数可以是一个RegExp对象或者一个字符串,第二个参数可以是一个字符串或者一个函...

524
来自专栏Python小屋

详解Python函数式编程之map、reduce、filter

map()、reduce()、filter()是Python中很常用的几个函数,也是Python支持函数式编程的重要体现。不过,在Python 3.x中,red...

3106
来自专栏C语言及其他语言

C语言中的基本输入输出

1.字符输出函数putchar putchar函数是字符输出函数,其功能是在终端(显示器)输出单个字符。其一般调用形式为: putchar(字符变量); ...

2769

扫描关注云+社区