• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

剑指offer(39)

剑指 Offer 39. 数组中出现次数超过一半的数字

难度279

数组中有一个数字的长度超过了数组长度的一半。请找到这个号码。

您可以假设数组是非空的,并且在给定的数组中总是有大多数元素。

示例 1:

输入: [1,2,3,2,2,2,5,4,2]

输出: 2

限制:

1=数组长度=50000

1.排序后取中间值。

类别解决方案{

公共:

int majorityElement(矢量数值){

sort(nums.begin()、nums . end());

int n=nums . size();

返回数字[n/2];

}

};

2.摩尔投票

原理是将所有模式记为1,其余记为-1,它们的和必须大于0;所以要遍历数组,先假设第一个数是模,如果和小于0,那就换模。

类别解决方案{

公共:

int majorityElement(矢量数值){

int majority=-1;

int CNT=0;

for(int I=0;inums . size();i ){

if(nums==多数){

cnt

}否则{

CNT-;

}

if(cnt0){

多数=nums

CNT=1;

}

}

返回多数;

}

};

Link to comment
Share on other sites