精华内容
下载资源
问答
  • 找出数组中出现次数超过一半的数字 欢迎关注作者简书 csdn传送门 题目   一个数组中有一个数字的次数超过了数组的一半,求出这个字符。如:int a[] = {2,3,2,2,2,2,2,5,4,1,2,3},求出超过一半的数字是2 分析...

    找出数组中出现次数超过一半的数字

    欢迎关注作者简书
    csdn传送门

    题目

      一个数组中有一个数字的次数超过了数组的一半,求出这个字符。如:int a[] = {2,3,2,2,2,2,2,5,4,1,2,3},求出超过一半的数字是2

    分析

    解法一

      数组中有一个数字出现的次数超过了数组长度的一半,如果把数组排序,排序之后位于数组中间的数字一定是出现次数超过数组长度一半的数字。排序算法可以使用sort(快排),它的时间复杂度为O(n*logn)。例如:{2,5,7,2,2,8,2,2}排序后为:{2,2,2,2,2,5,7,8} ,中位数2是出现次数超过一半的数字

    解法二

      基于Partition函数的O(n)算法
      Partition函数是实现快排的基础。同样是找中位数,受快速排序算法的启发,如果选中的数字的下标是n/2,那么这个数字就是中位数;如果选中的数字的下标大于n/2,则中位数在它的左边,可以接着在它左边部分的数组中查找;如果选中的数字的下标小于n/2,则中位数在它的右边,可以接着在它右边部分的数组中查找。这个过程是一个递归的过程。

    源码

    本题采用解法一

    /**
     * @program:
     * @description: 数组中出现次数超过一半的数字
     * @author: zhouzhixiang
     * @create: 2018-11-24 21:16
     */
    public class Test28 {
    
        /**
         * 找出数组中出现次数超过一半的数字
         * @param numbers
         * @return
         */
        public static Integer moreThanHalfNum(int[] numbers) {
            // 进行快速排序
            quickSort(numbers, 0, numbers.length-1);
            // 排序后的中位数即为目标值
            return numbers[numbers.length/2+1];
        }
    
        /**
         * 快速排序
         * @param numbers
         * @param left
         * @param right
         */
        private static void quickSort(int[] numbers, int left, int right) {
            if (left < right) {
                int key = numbers[left];
                int low = left;
                int high = right;
                while (low < high) {
                    while (low < high && numbers[low] < numbers[key])
                        low++;
                    numbers[high] = numbers[low];
                    while (low < high && numbers[high] > numbers[key])
                        high--;
                    numbers[low] = numbers[high];
                }
                numbers[low] = numbers[key];
                quickSort(numbers, left, low - 1);
                quickSort(numbers, low + 1, right);
            }
        }
    }
    
    

    欢迎加入Java猿社区
    欢迎加入Java猿社区.png

    展开全文
  • 排完序后,直接遍历,在遍历整个数组的同时统计每个数字的出现次数,然后把那个出现次数超过一半的数字直接输出,题目便解答完成了。总的时间复杂度为O(nlogn + n)。但如果是有序的数组呢,或者经过排序把无序的数组...

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

    解法一:

    如果无序,那么我们是不是可以先把数组中所有这些数字先进行排序(至于排序方法可选取最常用的快速排序)。排完序后,直接遍历,在遍历整个数组的同时统计每个数字的出现次数,然后把那个出现次数超过一半的数字直接输出,题目便解答完成了。总的时间复杂度为O(nlogn + n)。

    如果是有序的数组呢,或者经过排序把无序的数组变成有序后的数组呢?是否在排完序O(nlogn)后,还需要再遍历一次整个数组?

    我们知道,既然是数组的话,那么我们可以根据数组索引支持直接定向到某一个数。我们发现,一个数字在数组中的出现次数超过了一半,那么在已排好序的数组索引的N/2处(从零开始编号),就一定是这个数字。自此,我们只需要对整个数组排完序之后,然后直接输出数组中的第N/2处的数字即可,这个数字即是整个数组中出现次数超过一半的数字,总的时间复杂度由于少了最后一次整个数组的遍历,缩小到O(n*logn)。

    然时间复杂度并无本质性的改变,我们需要找到一种更为有效的思路或方法


    /**
    	 * 快速排序
    	 * 
    	 * @param arr
    	 *            带排序数组
    	 * @param low
    	 * @param high
    	 */
    	public static void quickSort(int[] arr, int low, int high) {
    		int i, j, temp, t;
    		if (low > high) {
    			return;
    		}
    		i = low;// i哨兵从左边开始
    		j = high;// j哨兵从右边开始
    
    		temp = arr[low];
    		while (i < j) {
    			// 从右边依次往左递减
    			while (temp <= arr[j] && i < j) {
    				j--;
    			}
    			// 从左边依次往右递增
    			while (temp >= arr[i] && i < j) {
    				i++;
    			}
    			// 如果满足条件则交换
    			if (i < j) {
    				t = arr[i];
    				arr[i] = arr[j];
    				arr[j] = t;
    			}
    		}
    		// 将基准位置与i和j相遇位置的数交换
    		arr[low] = arr[i];
    		arr[i] = temp;
    
    		// 递归调用左半数组
    		quickSort(arr, low, j - 1);
    		// 递归调用右半数组
    		quickSort(arr, j + 1, high);
    	}
    
    	/**
    	 * 对数组进行排序,已排好序的数组索引的N/2处(从零开始编号),就一定是这个数字
    	 */
    	public static int findNumber(int[] numbers) {
    		quickSort(numbers, 0, numbers.length - 1);
    		return numbers[numbers.length / 2];
    	}

    解法二:

    既要缩小总的时间复杂度,那么可以用查找时间复杂度为O(1)的hash表,即以空间换时间。哈希表的键值(Key)为数组中的数字,值(Value)为该数字对应的次数。然后直接遍历整个hash表,找出每一个数字在对应的位置处出现的次数,输出那个出现次数超过一半的数字即可。

    /**
    	 * 用查找时间复杂度为O(1)的hash表,即以空间换时间。<br>
    	 * 哈希表的键值(Key)为数组中的数字,值(Value)为该数字对应的次数。<br>
    	 * 然后直接遍历整个hash表,找出每一个数字在对应的位置处出现的次数,输出那个出现次数超过一半的数字即可。
    	 * 
    	 * @param numbers
    	 * @return
    	 */
    	public static int findNumber1(int[] numbers) {
    		Map<Integer, Integer> intToInt = new HashMap<>();
    		for (int n : numbers) {
    			if (!intToInt.containsKey(n)) {
    				intToInt.put(n, 1);
    			} else {
    				int value = intToInt.get(n);
    				intToInt.put(n, ++value);
    			}
    		}
    
    		for (Integer i : intToInt.keySet()) {
    			if (intToInt.get(i) > numbers.length / 2) {
    				return i;
    			}
    		}
    		return -1;
    	}

    解法三:

    Hash表需要O(n)的空间开销,且要设计hash函数,还有没有更好的办法呢?我们可以试着这么考虑,如果每次删除两个不同的数(不管是不是我们要查找的那个出现次数超过一半的数字),那么,在剩下的数中,我们要查找的数(出现次数超过一半)出现的次数仍然超过总数的一半。通过不断重复这个过程,不断排除掉其它的数,最终找到那个出现次数超过一半的数字。这个方法,免去了排序,也避免了空间O(n)的开销,总得说来,时间复杂度只有O(n),空间复杂度为O(1),貌似不失为最佳方法。

    /**
    	 * 每次删除两个不同的数(不管是不是我们要查找的那个出现次数超过一半的数字),<br>
    	 * 那么,在剩下的数中,我们要查找的数(出现次数超过一半)出现的次数仍然超过总数的一半。<br>
    	 * 通过不断重复这个过程,不断排除掉其它的数,最终找到那个出现次数超过一半的数字。
    	 * 
    	 * @param numbers
    	 * @return
    	 */
    	public static int findNumber2(int[] numbers) {
    		int i = 0;
    		int j = numbers.length - 1;
    		while (i <= j) {
    			if (numbers[i] == numbers[j]) {
    				j--;
    				i++;
    			} else {
    				numbers[i] = Integer.MAX_VALUE;
    				numbers[j] = Integer.MAX_VALUE;
    			}
    		}
    		for (int n : numbers) {
    			if (n != Integer.MAX_VALUE) {
    				return n;
    			}
    		}
    		return -1;
    	}

    解法四:

    更进一步,考虑到这个问题本身的特殊性,我们可以在遍历数组的时候保存两个值:一个candidate,用来保存数组中遍历到的某个数字;一个nTimes,表示当前数字的出现次数,其中,nTimes初始化为1。当我们遍历到数组中下一个数字的时候:

    • 如果下一个数字与之前candidate保存的数字相同,则nTimes加1;
    • 如果下一个数字与之前candidate保存的数字不同,则nTimes减1;
    • 每当出现次数nTimes变为0后,用candidate保存下一个数字,并把nTimes重新设为1。 直到遍历完数组中的所有数字为止。

    /**
    	 * 可以在遍历数组的时候保存两个值:一个candidate,用来保存数组中遍历到的某个数字<br>
    	 * ;一个nTimes,表示当前数字的出现次数,其中,nTimes初始化为1。当我们遍历到数组中下一个数字的时候:<br>
    	 * 如果下一个数字与之前candidate保存的数字相同,则nTimes加1;<br>
    	 * 如果下一个数字与之前candidate保存的数字不同,则nTimes减1;<br>
    	 * 每当出现次数nTimes变为0后,用candidate保存下一个数字,并把nTimes重新设为1。<br>
    	 * 直到遍历完数组中的所有数字为止。
    	 * 
    	 * @param number
    	 * @return
    	 */
    	public static int findNumber3(int[] numbers) {
    		int nTimes = 1;
    		int candidate = numbers[0];
    		for (int i = 1; i <= numbers.length - 1; i++) {
    			if (nTimes == 0) {
    				candidate = numbers[i];
    				nTimes = 1;
    			} else {
    				if (candidate == numbers[i]) {
    					nTimes++;
    				} else {
    					nTimes--;
    				}
    			}
    		}
    
    		return candidate;
    	}

    展开全文
  • 现在用一种时间复杂度为O(n)的方法:因为出现次数超过一半,即剩下的的个数的累计和都小于这个的个数,我们用抵消原则,用这个与其余相抵消,剩下的那个必然是所求。具体操作:取一个关键值key记录...

    思路分析:

          出现次数超过一半,可以直接排序 得到中间的数即为所求,时间复杂度为排序的复杂度O(nlogn)

    现在用一种时间复杂度为O(n)的方法:因为出现的次数超过一半,即剩下的数的个数的累计和都小于这个数的个数,我们用抵消原则,用这个数与其余数相抵消,剩下的那个数必然是所求。具体操作:取一个关键值key记录数组中出现的书,用value记录这个数出现的次数,遍历数组,如果和这个数字相同,则加1,如果不等则减1,当出现的次数为0,则取下一个数字为key,重置value=1,最后key即为所求。

    代码:c++

    #include<iostream>
    #include<vector>
    using namespace std;
    int findMoreThanHalf(vector<int> v){
        int len=v.size();
        if(len==0)
            return 0;//无效输入
        int key=v[0];
        int value=1;
        for(int i=1;i<len;++i){
            if(value==0){
                key=v[i];
                value=1;
            }
            if(key==v[i]){   
                value++;
            }
            else
                value--;
        }//得出key即为所求,在存在的情况下
    //判断出现超过一半的数是否存在
        value=0;
        for(int i=0;i<len;++i){
             if(key==v[i])
                 value++;
        }
        if(value<=len/2)
             return 0;//无效输入
        else
             return key;
    }
         
            
    

     

    展开全文
  • 问题描述: 在编程之美中有这样一个问题:如何找出数组或其它连续存储空间中某个关键字出现次数大于总数一半...即每次去掉两个不相同的值,则剩下的那些数出现次数超过一半与缩小前不变。这样就可以将将数据缩小在

    问题描述:

    在编程之美中有这样一个问题:如何找出数组或其它连续存储空间中某个关键字出现次数大于总数一半的那个值。对于这个问题解决办法较多,现在将部分方法罗列如下。

    1,可以采用哈希表法,即将其进行哈希运算,在对统计次数排序,再找出其中出现次数最多的那个。
    2,编程之美中所提出的缩小规模算法。即每次去掉两个不相同的值,则剩下的那些数出现次数超过一半的数与缩小前不变。 这样就可以将将数据缩小在一个很小的范围内解决(经典)。
    3,运用计数器进行解决(这种办法空间和时间复杂度都很好)下面将其解法贴出。为了解决方便我们以数组为例.
    int find (int a[], int len)
    {
    	int temp;
    	int i;
    	temp = a[0];
    	int count = 1;
    	for(i = 1;i < len; i++)
    	{
    		if(temp == a[i])
    			count++;
    		else
    			count--;
    		if(count==0)
    		{
    			temp = a[i];
    			count=1;
    		}
    	}
    	return temp;
    }
    


    展开全文
  • 主要介绍了PHP实现找出数组中出现次数超过数组长度一半的数字算法,涉及php数组的遍历、统计、判断等相关操作技巧,需要的朋友可以参考下
  • 39. 数组中出现次数超过一半的数字 解题思路 多数投票问题,可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题,使得时间复杂度为 O(N)。 使用 cnt 来统计一个元素出现的次数,当遍历到的元素和统计元素...
  • 给出n个,需要我们找出出现次数超过一半,下面小编给大家分享下我的实现思路及关键代码,感兴趣的朋友一起学习吧
  • 数组中有一个数字出现次数超过数组长度的一半,请找出这个数字。 计数+比较 不考虑效率,采用最简单的办法,遍历数组,使用 List 的 count() 方法统计元素出现的次数: def more_than_half_num(arr): half = len...
  • 问题是这样的,有一组,里面有各种数据,现在需要出来一个,它的出现的频率超过一半。 题目很简单,最直接的想法就是把数组排序,这样最中间的肯定就是需要。原理是这个占了数组的一半,而且...
  • 现在有一个数组,已知一个数出现次数超过一半,请用O(n)的复杂度的算法找出这个。 解法 方法一:创建一个unordered_map,key为数组中的,value为此数出现的次数。遍历一遍数组,用unordered_map统计每个...
  • * 数组中有一个数字出现次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0 * * @...
  • 先对数组进行排序,出现次数超过一半的数组元素一定是该数组的中位 这里使用效率比较好的双指针快排 /** * 基于快排算法 */ public static int findNumberBySort(int[] array) { if (array == null
  • 主要介绍了Python 找出出现次数超过数组长度一半的元素实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 答案: 创建一个hash_map,key为数组中的,value为此数出现的次数。...但是没有利用“一个数出现次数超过一半”这个特点。也许算法还有提高的空间。 答案2: 使用两个变量A和B,其中A存储某个数组
  • 题目:如何在O(n)的时间复杂度内找出数组中出现次数超过一半。 由于本题对时间复杂度有要求,所以可采用以下2种方法。方法一:每次取出两个不同的,剩下的数字中重复出现的数字肯定比其他数字多,将规模...
  • 算法--找出数组中出现次数超过一半 作者:陈太汉 算法--找出数组中出现次数超过一半  每当我看到经典的算法题,就怀念高中,感觉很多算法题就是高中的题目,谁叫哥只读了个专科,高数基本相当没学。 ...
  • 快速找出数组中出现次数超过一半的数字

    万次阅读 热门讨论 2018-07-09 22:04:45
    面试题29:数组中出现次数超过一半的数字 题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的...
  • 找出数组中出现次数超过一半,现在有一个数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个。 这道题在网上已经有了很多种解法,如果先排序在查找,那么n/2这个位置一定就只要找的...
  • 【牛客网刷题】—找出数组中出现次数超过数组大小一半的数字 题目如下: 思路:本题打眼一看容易让人想到用一个计数器把每个数字都记录一边,但是这个想法是很混沌的,非常难以实现,因为这是一个无序的数组。我的...
  • 1. 找出数组中出现次数超过一半 给定数组,要求找出数组中出现次数超过数组长度一半的。 2. 解法解法: 方法一:先将数组中的元素排序,由于目标元素的数量超过数组长度的一半,故排序后数组的中间元素...
  • /*面试题29:数组中出现次数超过一半的数字 :数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 */ /* 解题思路:1.首先需要判断输入的数组是否有效。 2.数组中有一个数字出现的次数超过数组...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,041
精华内容 11,616
关键字:

找出出现次数超过一半的数