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

推荐

peter7788

方法一：采用用户“分形叶”思路（注意到目标数超过数组长度的一半，对数组同时去掉两个不同的数字，到最后剩下的一个数就是该数字。如果剩下两个，那么这两个也是一样的，就是结果），在其基础上把最后剩下的一个数字或者两个回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。

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)

MSean

思路一：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。（比如：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)

Epiphany_now

题目限制条件数字是小于等于 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)

Java

望向路途

题目给定明确数值大小，直接定义数组，下标为值，数值为数字的数量

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)

Java

枉做好人

    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)

Python 3

曰无衣bupt

一个一个的检查太麻烦了，而且对于大的数组时间复杂度更高。

直接借助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)

txy_钟琛

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)

Python 3

Vivimore

在保证一定有解的情况下，可以使用这种方法时间复杂度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)

C++

牛客嗷嗷

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)

C++

牛客730705474号

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)

Python 3

JaydenCheng

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)

Python 3

长歌行abc

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)

Java

together"

遍历数组，同时用一个 Map<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)

C++

恨别鸟惊心

暴力循环...
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)

Java

男神20190129221786

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)

Javascript

会飞得猿

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)

C++

riky

摩尔投票法：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() <= 0) return 0;
        int ans = 0;
        int cnt = 0;
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(cnt == 0)
                ans = numbers[i], ++cnt;
            else{
                if(ans != numbers[i])
                    --cnt;
                else 
                    ++cnt;
            }
        }
        return ans;
    }
};

发表于 2021-08-21 16:18:27 回复(0)

Java

牛客慧

//(借鉴)摩尔投票法
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int vote=0;
        int moreN=array[0];
        for(int i=0;i<array.length;i++){
            if(vote==0) moreN=array[i];
            if(array[i]==moreN){
                vote++;
            }else{
                vote--;
            }
        }
        return moreN;
    }
}

发表于 2021-08-18 21:12:33 回复(0)

C++

EriccCartman

第三种方法真的牛逼。

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int index = 0;
        int value = 0;
        for(int i = 0; i < numbers.size();i++){
            if(index==0) {
                value = numbers[i];
                index++;
            } else {
                if(value==numbers[i]) index++;
                else index--;
            }
        }
        return value;
    }

发表于 2021-08-13 18:26:35 回复(0)

Java

大厂绝缘体

public class Solution {
    //O(n)的时间  O(1)的空间
    public int MoreThanHalfNum_Solution(int [] array) {
        int val = 0;
        int count = 0;
        for(int x : array){
            if(count == 0){
                val = x;
                count++;
            }else{
                if(x == val) count++;
                else count--;
            }
        }
        return val;
    }
}

发表于 2021-08-10 20:25:04 回复(0)

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

输入描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题