【试题描述】数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
【试题分析】时间复杂度O(n),空间复杂度O(1)
思路1:
创建一个hash_map,key为数组中的数,value为此数出现的次数。遍历一遍数组,用hash_map统计每个数出现的次数,并用两个值存储目前出现次数最多的数和对应出现的次数。 这样可以做到O(n)的时间复杂度和O(n)的空间复杂度,满足题目的要求。 但是没有利用“一个数出现的次数超过了一半”这个特点。也许算法还有提高的空间。 思路2: 使用两个变量A和B,其中A存储某个数组中的数,B用来计数。开始时将B初始化为0。 遍历数组,如果B=0,则令A等于当前数,令B等于1;如果当前数与A相同,则B=B+1;如果当前数与A不同,则令B=B-1。遍历结束时,A中的数就是要找的数。 这个算法的时间复杂度是O(n),空间复杂度为O(1)。【参考代码】
1 int findMoreThanHalf(int[] arr) { 2 if (null == arr) 3 return -1; 4 5 int nValue = arr[0]; 6 int count = 1; 7 for (int i = 1; i < arr.length; i++) { 8 if (nValue == arr[i]) { 9 count++;10 } else {11 if (count == 0) {12 nValue = arr[i];13 count = 1;14 }15 count--;16 }17 }18 return nValue;19 }