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

相关文章

来自专栏WD学习记录

Leetcode ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of ...

662
来自专栏Bingo的深度学习杂货店

三个数的和小于等于k

给一个数组以及一个数K, 从这个数组里面选择三个数,使得三个数的和小于等于K, 有多少种选择的方法?(不包括重复的情况) Example: Input: nu...

3515
来自专栏互联网杂技

排序算法性能比较

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

3327
来自专栏数据结构与算法

30:字符环

30:字符环 总时间限制: 1000ms 内存限制: 65536kB描述 有两个由字符构成的环。请写一个程序,计算这两个字符环上最长连续公共字符串的长度。例...

4169
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1002
来自专栏PPV课数据科学社区

数据结构常见的八大排序算法

前言 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下: 他们的性能...

47311
来自专栏Java开发者杂谈

算法之数组和问题

算法题之数组和求解 数组和问题 ​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出...

3568
来自专栏猿人谷

单链表

线性表的链式表示和实现       线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以使不连续的)。因此,为...

2435
来自专栏desperate633

LintCode 堆化代码

311
来自专栏和蔼的张星的图像处理专栏

46. 主元素解1解2

给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。假定一定存在这样的主元素。 样例 给出数组[1,1,1,1,2,2,2],...

652

扫码关注云+社区