首页 > 试题广场 >

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

[编程题]数组中出现次数超过一半的数字
  • 热度指数:845698 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。

数据范围:,数组中元素的值
要求:空间复杂度:,时间复杂度

输入描述:
保证数组输入非空,且保证有解

示例1

输入

[1,2,3,2,2,2,5,4,2]

输出

2
示例2

输入

[3,3,3,3,2,2,2]

输出

3
示例3

输入

[1]

输出

1
推荐
方法一:采用用户“分形叶”思路(注意到目标数 超过数组长度的一半,对数组同时去掉两个不同的数字,到最后剩下的一个数就是该数字。如果剩下两个,那么这两个也是一样的,就是结果),在其基础上把最后剩下的一个数字或者两个回到原来数组中,将数组遍历一遍统计一下数字出现次数进行最终判断。
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
            if(array==null||length<=0){
                return 0;
            }
            
            if(length==1){
                return array[1];
            }
            
            int[] tempArray=new int[length];
            for(int i=0;i<length;i++){
                tempArray[i]=array[i];
            }
            
            for(int i=0;i<length;i++){
                //后面需要用零来代表抹除数字,所以对0时做特殊处理
                if(tempArray[i]==0){
                    continue;
                }
                
                for(int j=i+1;j<length;j++){
                    if(tempArray[i]!=tempArray[j]&&tempArray[j]!=0){
                        tempArray[i]=0;//此处用0代表抹去该数字
                        tempArray[j]=0;
                        break;
                    }
                    
                }
            }
            
            for(int i=0;i<length;i++){
                System.out.println(tempArray[i]);
            }
            
            //找出未被抹去的数字
            int result=0;
            for(int i=0;i<length;i++){
                if(tempArray[i]!=0){
                    result=tempArray[i];
                    break;
                }
            }
            
            int times=0;
            for(int i=0;i<length;i++){
                if(result==array[i]){
                    
                    times++;
                }
            }
            
            if(times*2<length){
                result=0;
            }
            return result;
    }
}

方法二:剑指offer解法二(个人觉得与方法一基本就是同一个意思,异曲同工之妙)
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
        if(array==null||length<=0){
            return 0;
        }
        
        int result=array[0];
        int times=1;
        for(int i=1;i<length;i++){
            if(times==0){
                result=array[i];
                times=1;
            }else{
                if(array[i]==result){
                    times++;
                }else{
                    times--;
                }
            }
        }
        
        times=0;
        for(int i=0;i<length;i++){
            if(result==array[i]){
                times++;
            }
       }
            
       if(times*2<length){
           result=0;
       }
       return result;
    }
}


编辑于 2015-06-19 17:18:47 回复(111)
public static int MoreThanHalfNum_Solution(int[] array) {
        if(array==null)
            return 0;
        HashMap<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
        for (int i = 0; i < array.length; i++) {
            if(!hashMap.containsKey(array[i])){
                hashMap.put(array[i], 1);
            }else{
                
                int count=hashMap.get(array[i]).intValue();
                hashMap.put(array[i], ++count);
            }
        }
        Iterator<Entry<Integer, Integer>> iter=hashMap.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry entry=(Entry) iter.next();
            int target=(Integer) entry.getKey();
            int count=(Integer) entry.getValue();
            if(count>array.length/2){
                return target;
            }
        }
        
        return 0;

    }

发表于 2015-04-28 22:20:25 回复(1)
利用HashMap存出现的个数,没出现过的就放进去,出现过的就累加!
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer, Integer> map = new HashMap<>();
        int i = 0;
        while(i<array.length){
            if(map.containsKey(array[i])){
                map.put(array[i],map.get(array[i])+1);
            }else{
                map.put(array[i],1);
            }
            i++;
        } 
        for(Entry<Integer, Integer> e : map.entrySet()){
            if(e.getValue() > array.length/2){
                return e.getKey();
            }
        }
        return 0;
    }
}
发表于 2017-09-19 13:32:50 回复(0)
java实现
测试数据中有一些数据不存在出现次数超过一半的数,并且不存在的情况下要返回0,略坑。
本题O(n)的思想是,定义两个变量temp和count,每次循环时,如果array[i]的值等于temp,则count自增一,如不等并且count>0,则count自减一,若array[i]的值不等于temp并且count不大于0,重新对temp赋值为当前array[i],count赋值为1。
如存在大于一半的数,直接返回temp就是了,但测试数据中有不存在的情况,所以最后又来了一遍校验,检查当前temp值是否出现过一半以上。
 public int MoreThanHalfNum_Solution(int [] array) {
        int count = 0;
		int temp = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == temp) {
				count++;
			} else if (count > 0) {
				count--;
			} else {
				temp = array[i];
				count = 1;
			}
		}
        //验证
        count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==temp)
            count++;
        }
		return count > array.length/2 ? temp : 0;
    }

发表于 2015-10-05 16:55:04 回复(1)
思路一:数组排序后,如果符合条件的数存在,则一定是数组中间那个数。(比如:1,2,2,2,3;或2,2,2,3,4;或2,3,4,4,4等等)
这种方法虽然容易理解,但由于涉及到快排sort,其时间复杂度为O(NlogN)并非最优;
参考代码如下:
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
        // 因为用到了sort,时间复杂度O(NlogN),并非最优
    	if(numbers.empty()) return 0;
        
        sort(numbers.begin(),numbers.end()); // 排序,取数组中间那个数
        int middle = numbers[numbers.size()/2];
        
        int count=0; // 出现次数
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i]==middle) ++count;
        }
        
        return (count>numbers.size()/2) ? middle :  0;
    }
};
思路二:如果有符合条件的数字,则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值:一是数组中一个数字,一是次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码如下:
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
    	if(numbers.empty()) return 0;
        
        // 遍历每个元素,并记录次数;若与前一个元素相同,则次数加1,否则次数减1
        int result = numbers[0]; 
        int times = 1; // 次数
        
        for(int i=1;i<numbers.size();++i)
        {
            if(times == 0)
            {
                // 更新result的值为当前元素,并置次数为1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result)
            {
                ++times; // 相同则加1
            }
            else
            {
                --times; // 不同则减1                
            }
        }
        
        // 判断result是否符合条件,即出现次数大于数组长度的一半
        times = 0;
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i] == result) ++times;
        }
        
        return (times > numbers.size()/2) ? result : 0;
    }
};

编辑于 2016-08-23 16:04:29 回复(55)
题目限制条件 数字是小于等于 10000的   空间复杂度 O(1)
只需要创建一个长度为10000的数组a。遍历一遍目标数组,把目标数组每个数在a数组对应下标的数字加1,最后就得到了数字出现的次数,在遍历一遍数组a,找出大于  length/2的元素  
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int[] a=new int[10000];
        for(int i=0;i<array.length;i++){
            a[ array[i] ]+=1;
        }
        float num=array.length/2;
        for(int i=0;i<10000;i++){
            if(a[i] > num) return i;
        }
        return 0;
         
    }
}

发表于 2022-08-06 18:08:59 回复(0)
function MoreThanHalfNum_Solution(numbers) {
  // write code here
  if (numbers.length === 1) return numbers[0];
  let map = new Map();
  for (let i = 0; i < numbers.length; i++) {
    if (map[numbers[i]]) {
      map[numbers[i]] += 1;
    } else {
      map[numbers[i]] = 1;
    }
  }
  for (let key in map) {
    if (map[key] > numbers.length / 2) return key;
  }
}
module.exports = {
  MoreThanHalfNum_Solution: MoreThanHalfNum_Solution,
};

发表于 2022-08-06 01:15:40 回复(0)
题目给定明确数值大小,直接定义数组,下标为值,数值为数字的数量
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int l=array.length;
        int result=0;
        int[] res=new int[10001];
        for(int i:array){
            res[i]++;
            if(res[i]>(l/2)){
                result=i;
            }
        }
        return result;
    }
}

发表于 2022-07-08 09:01:50 回复(0)
    public int MoreThanHalfNum_Solution(int [] array) {
        //摩尔投票法
        int n = array.length;
        int count = 0;
        int res = -1;
        for (int i = 0; i < n; i++) {
            if (count == 0){
                res = array[i];
                count ++;
            }else if (array[i] != res){
                count--;
            }else if (array[i] == res){
                count ++;
            }
        }
        return res;
    }

发表于 2022-06-30 13:33:47 回复(0)
一个一个的检查太麻烦了,而且对于大的数组时间复杂度更高。
直接借助set:
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in set(numbers):
            if numbers.count(i)>len(numbers)/2:
                return i


发表于 2022-06-15 17:44:00 回复(0)
import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int ans = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num: array) {
            if (map.containsKey(num)){
                int count = map.get(num);
                count++;
                if (count > array.length/2){
                    ans = num;
                    break;
                }
                map.put(num,count);
            }else {
                map.put(num,1);
            }
        }
        if (map.size() == 1){
            return array[0];
        }
        return ans;
    }
}

发表于 2022-05-27 11:51:03 回复(0)

在保证一定有解的情况下,可以使用这种方法 时间复杂度O(n) 空间复杂度O(1)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        temp = -1
        cnt = 0
        for num in numbers:
            if cnt == 0:
                temp = num
                cnt += 1
            else:
                if num == temp:
                    cnt += 1
                else:
                    cnt -= 1
        return temp

哈希法
时间复杂度:O(n) 空间复杂度O(n)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        n = len(numbers)
        mp = {}
        for num in numbers:
            if num not in mp:
                mp[num] = 1
            else:
                mp[num] += 1
            if mp[num] >= n / 2:
                return num
发表于 2022-05-18 21:47:51 回复(0)
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
    }
};

发表于 2022-03-30 18:03:12 回复(0)
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int count = 1;
        int cur = numbers[0];
        int pre = 0;
        for(int i = 1;i < numbers.size();i++){
            if(numbers[i]!=cur&&count==1){
                if(pre==numbers[i]){
                    cur = pre;
                    count++;
                }
                else{
                    pre = cur;
                    cur = numbers[i];
                }

            }
            else if(numbers[i]!=cur){
                count--;
            }
            else{
                count++;
            }
        }
        return cur;
    }
};

发表于 2022-02-25 16:18:29 回复(0)
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        half_len = len(numbers)/2
        num_dic = {}
        for i in numbers :
            num_dic[i] = num_dic.get(i, 0) + 1
            if num_dic[i] >= half_len :
                return i

发表于 2022-02-17 20:41:44 回复(0)
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int sign = numbers.size() / 2;
        
        //设一个包含所有数的数组
        vector<int> arr;
        arr.resize(50000);
        
        //numbers数组中每个数出现一次,则arr数组对应的下标就加1,
        for(int i = 0; i < numbers.size(); i++)
        {
            arr[numbers[i]]++;
        }
        
        //找出arr数组大于sign的数,若大于,则下标就是要找的数;
        int ret = 0;
        for(int i = 0; i < arr.size(); i++)
        {
            if(arr[i] > sign)
            {
                ret = i;
                break;
            }
        }
        
        return ret;
    }
};

发表于 2022-01-11 18:55:50 回复(0)
w=input()
w=w[1:-1]
w=list(map(int,w.split(",")))
l=len(w)/2 w=sorted(w)
d={} for i in w:
    d[i]=d.get(i,0)+1 w=list(set(w)) for i in w: if(d[i]>l): print(i)
发表于 2021-09-14 18:03:32 回复(0)
遍历数组,同时用一个 Map<integer> 记录每个元素的出现次数,超过一半时直接返回即可。</integer>
<integer>
import java.util.*;

public class Solution {

    // HashMap计数
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        // 处理数组长度只有1的特殊情况
        if (array.length == 1) {
            return array[0];
        }

        int threshold = array.length / 2;
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int num : array) {
            Integer cnt = cntMap.get(num);
            if (cnt == null) {
                cntMap.put(num, 1);
            } else if (cnt == threshold) {
                return num;
            } else {
                cntMap.put(num, cnt + 1);
            }
        }
        return -1;
    }
}


如果先对数组进行排序,那么出现次数超过一半的元素一定是数组的中位数,也就是排序后下标为n/2的那个元素(n为偶数时n/2是中间偏右的那个元素,n为奇数时n/2就是中间元素),所以我们的目标就是找到排序后下标为n/2的那个元素。这其实可以借助快速排序来实现:

快排的分区函数每次找到一个pivot放到数组的适当位置,将数组分为左右两个部分,左边元素都小于pivot,右边元素都大于pivot。此时如果pivot的下标i正好是n/2,那pivot就是出现次数超过一半的那个元素,返回它即可;如果i<n/2,那就对i的右半部分执行分区函数;如果i>n/2,那就对i的左半部分执行分区函数。总之最终一定能找到i==n/2的目标元素,《剑指Offer》给出的时间复杂度是O(n)。

public class Solution {

    // 快速排序思想
    // 时间复杂度O(n)
    // 空间复杂度O(1)
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int l = 0, r = array.length - 1;
        int target = array.length / 2;
        while (true) {
            int mid = partition(array, l, r);
            if (target == mid) {
                return array[target];
            } else if (target > mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }

    // 快排的分区函数
    public int partition(int[] array, int l, int r) {
        int i = l, j = r, pivot = array[l];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            array[i] = array[j];
            while (i < j && array[i] < pivot) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = pivot;
        return i;
    }
}

我们首先给出 Boyer-Moore 算法的详细步骤:

  • 维护一个候选众数candidate和它出现的次数count。初始时candidate为首元素,count为 0;

  • 我们遍历数组array中的所有元素,对于每个元素 x,进行如下判断:

    • 在判断 x 之前,如果count的值为 0,我们先将 x 的值赋予candidate,随后我们判断 x:

      • 如果 x 与candidate相等,那么计数器count的值增加 1;

      • 如果 x 与candidate不等,那么计数器count的值减少 1。

  • 在遍历完成后,candidate即为整个数组的众数。

public class Solution {

    // 投票算法
    // 我个人觉得就是把本来对自己+1的票数,转化为对候选者的票数-1,这就等同于变相给自己投票了
    // 时间复杂度O(n)
    // 空间复杂度O(1)
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int candidate = array[0], cnt = 1;
        for (int i = 1; i < array.length; i++) {
            if (candidate == array[i]) { // 候选者票数+1
                cnt++;
            } else if (cnt > 0) { // 候选者票数-1, 相当于变相对array[i]的票数+1
                cnt--;
            } else { // 暂时没有候选者, 那就让array[i]作为候选者, 票数为1
                candidate = array[i];
                cnt = 1;
            }
        }

        return candidate;
    }

}


</integer>
发表于 2021-09-07 17:21:40 回复(0)
暴力循环...
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 1 || numbers.size() == 2){
            return numbers[0];
        }
        for(int i = 0; i < numbers.size(); i++){
            int c = 0;
            for(int j = 0; j < numbers.size(); j++){
                if(numbers[j] - numbers[i] == 0 && j != i)
                    c++;
            }
            if(c + 1 > numbers.size() / 2){
                return numbers[i];
            }
        }
        return 0;
    }
};

发表于 2021-08-29 23:44:24 回复(0)
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //摩尔投票
        int cnt = 0;
        int candidate = 0;
        for(int num : array){
            if(cnt == 0)
                candidate = num;
            cnt += candidate == num ? 1 : -1;
        }
        return candidate;
            
    }
}

发表于 2021-08-27 11:13:21 回复(0)
function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    var count = 0;
    var res = 0;
    for (var i = 0; i < numbers.length; i++) {
        if (count == 0) {
            res = numbers[i];
        }
        if (numbers[i] == res) {
            count++;
        } else {
            count--;
        }
    }
    console.log(res);
    return res;
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};
这是我的js代码,通过了。从头开始遍历,相等加1最后打印自减,若值至0,则进入上一步的判断,不至0,则进行下一步。

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    if (numbers.length == 1) {
        return numbers[numbers.length - 1];
    }
    // 排序
    numbers.sort();
    // 新建一个对象 将每个数出现的次数与此数组成键值对
    var obj = {}
    for (var i = 0; i < numbers.length; i++) {
        if (numbers[i] == numbers[i + 1] && numbers[i] != numbers[i - 1]) {//判断是否重复,是否已经放入容器
            var result = numbers[i];
            // console.log(result);
            var count = numbers.lastIndexOf(result) - numbers.indexOf(result) + 1;
            // console.log(count);
            // count 与 result组成键值对 做一个绑定
            obj[count] = result
            // console.log(obj[count]);
        }
    }
    // 此时对象中的key 是 count
    // 先获取到最大的key 与 numbers.length / 2 作比较 
    // 最终通过key获取value  这样就不会出现错乱了
    if (Math.max.apply(null, Object.keys(obj)) >= numbers.length / 2) {
        return obj[Math.max.apply(null, Object.keys(obj))];
    }
    else {
        return -1;
    }
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};


另一种方法,比较蠢,用了三个数组实现。其中所以为了保证 每一个数出现的次数与这个数能够有一个绑定关系  我用了一个对象将count与result做了绑定  这样的话 算出每个属性最大的key值与numbers.length / 2作比较  大于等于的应该就是出现次数最多的那个key 再通过这个key找到value 就能正确匹配值了 .
发表于 2021-08-27 09:18:38 回复(0)