首页 > 其他分享 >P52 数组中出现次数超过一半的数字

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

时间:2024-01-14 21:13:56浏览次数:31  
标签:cnt val nums int 次数 数组 P52

题目链接:

方法一:
若数组中有数字的出现次数超过数组长度的一半(绝对众数),则将该数组排序后中间位置的数一定就是该数。

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n / 2];
    }
};

方法二、摩尔投票算法

用于解决绝对众数问题,主要思想为:“捉对厮杀”
维护一个变量val,初始化为数组的第一个元素,cnt用于记录val的出现次数,初始时为1。从前到后遍历数组,如果元素和val相同就将cnt++,表示出现次数+1,否则就将val赋值为当前元素并将cnt更新为1。由于绝对众数的出现次数大于数组长度的一半,其出现次数在经过如此的“抵消”过程后一定>0,val最后的值即为绝对众数。

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 1, val = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (val == nums[i]) cnt++;
            else cnt--;
            if (cnt == 0) {
                val = nums[i];
                cnt = 1;
            }
        }
        return val;
    }
};

标签:cnt,val,nums,int,次数,数组,P52
From: https://www.cnblogs.com/pangyou3s/p/17964193

相关文章

  • [刷题技巧] LeetCode238. 除自身以外数组的乘积
    题目描述思路:前缀/后缀乘积数组构造除自身以外数组的左边前缀乘积构造除自身以外数组的右边后缀乘积然后对应位置相乘方法一:classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;//前缀乘积数组:leftProduct[i]表......
  • 数组
    数组介绍数组可以存放多个同一类型的数据。数组也是一种数据类型,是引用类型。数组的快速入门//1.double[]表示是double类型的数组,数组名hens//2.{3,5,1,3.4,2,50}表示数组的值/元素,依次表示数组的//第几个元素//double[]hens={3,5,1,3.4,2,50,7.8......
  • [刷题班] LeetCode1480. 一维数组的动态和
    题目描述思路:前缀和前缀和数组(prefixSum)的构造方法一:classSolution{publicint[]runningSum(int[]nums){int[]preSum=newint[nums.length];preSum[0]=nums[0];for(inti=1;i<nums.length;i++){preSum[i]......
  • js 合并、复制和修改定型数组
    定型数组同样使用数组缓冲来存储数据,而数组缓冲无法调整大小。因此,下列方法不适用于定型数组:concat()pop()push()shift()splice()unshift()不过,定型数组也提供了两个新方法,可以快速向外或向内复制数据:set()和subarray()。set()从提供的数组或定型数组中把值复制到当前定型数组......
  • js 定型数组行为
    //创建一个长度为6的Int32Arrayconstints2=newInt32Array(6);//每个数值使用4字节,因此ArrayBuffer是24字节alert(ints2.length);//6//类似DataView,定型数组也有一个指向关联缓冲的引用alert(ints2.buffer.byteLength);//24//创建一个包含[2,4,6,8]的Int......
  • [刷题班] LeetCode80. 删除有序数组中的重复项II
    题目描述思路:快慢指针slow指针指向已经处理元素的下一个位置因为数组有序,如果nums[fast]==nums[slow-2],那么nums[fast]肯定等于nums[slow-1],那么此时这个数就出现了三次。此时slow保持不变,fast继续遍历。关键:nums[fast]!=nums[slow-2]方法一:classSolution{......
  • [刷题班] LeetCode26. 删除有序数组中的重复项
    题目描述思路:快慢指针slow指针:指向已经处理的区域(没有重复元素)的最后一个位置fast指针:指向当前正在处理的元素方法一:classSolution{publicintremoveDuplicates(int[]nums){intslow=0,fast=0;for(;fast<nums.length;fast++){......
  • 字符指针与字符数组的初始化
    字符指针可以初始化赋值一个字符串,字符数组初始化也可以赋值一个字符串。两者的区别是什么呢?#include<stdio.h>#include<string.h>intmain(){char*p="hello";//把字符串常量"hello"的首地址赋给pcharc[10]="hello";//等价于strcpy(c,"hello");c[......
  • 柔性数组——《初学C语言第56天》
    //////————柔性数组(柔性数组在结构体中只能存在一个)////C99中,结构体中的最后一个元素(成员变量)允许是未知大小的数组,这就叫做“柔性数组”成员。//typedefstructst_type//{// inti;// inta[0];//柔性数组成员//}type_a;////有些编译器会报错无法编译可以改成://type......
  • 类模板实现简单的数组
    //Myarray.hpp#pragmaoncetemplate<classT>classMyArray{public: MyArray(intcapacity){ this->mCapacity=capacity; this->msize=0; this->p=newT[this->mCapacity]; } //copy MyArray(constMyArray&arr){ this->......