小程序开发平台花多少钱宁波seo网站排名优化公司

数组中出现次数超过一半的数字，这道题出自《剑指Offer》。
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
这里共有三种解法

思路1：

因为要找的数字已经超过长度的一半，我们可以之间把这个数组排序，那么这个数一定会出现在数组的中间。

C语言代码

可以使用，冒泡或者快排等其他算法，我这里直接用 qsort函数

//排序规则
int cmp_int(const void* s1,const void* s2);
int majorityElement(int* nums, int numsSize){qsort(nums,numsSize,sizeof(nums[0]),cmp_int);int i = 0;return nums[numsSize/2];
}
int cmp_int(const void* s1,const void* s2)
{return *(int*)s1 - *(int*)s2;
}

Java代码

public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}

思路2：

我们可以记录每个数字出现的次数，然后判断最大的那个是不是超过数组长度的一半，C语言有点麻烦就不写了，不过Java可以用HasMap。

Java代码

public int majorityElement(int[] nums) {HashMap<Integer,Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int tmp = nums[i];if (map.get(tmp) == null) {map.put(tmp,1);}else{map.put(tmp,map.get(tmp)+1);}if (map.get(tmp) > nums.length/2) {return tmp;}}return 0;}

思路三:

现在我们可以换一种思路来想，一个数如果操作数组长度的一半，那么也就是说这个数字的个数比数组其他数字加起来还要多。

那么我们就可以这么做，在遍历数组的时候，记录两个值，一个是数组中的一个数字，另一个则是这个数字的次数，如果遍历到下一个数字和当前记录的数字相同，次数加1，如果不相同个数就减去1，当次数为0时，我们就需要保存下一个数字并把该数字的次数设置为1。

那么最后一个次数为1或者大于等于1的，那么这个数就极有可能就时我们要找的那个数字。
这个思路就类似与拿数组两个不相同的数字之间抵消，因为有个数的个数是大于数组一半的，那么最后的那个数就是我们要找的那个数。

C语言代码

int majorityElement(int* nums, int numsSize){int result = nums[0];//数字int count = 1;//数字出现的字数int i = 0;for (i = 1; i < numsSize; i++) {if (count == 0){//但次数为0的时候,更换成当前数字,并把次数设置为1result = nums[i];count = 1;}else if (nums[i] == result){count++;}else{count--;}}//再次判断该数字个数是否是超过数组长度一半的数字count = 0;for (i = 0; i < numsSize; i++){if (nums[i] == result){count++;}}if (count > numsSize/2){return result;}return -1;
}

Java代码

public int majorityElement(int[] nums) {if (nums == null) {return 0;}//数字int result = nums[0];//数字出现的次数int count = 1;for (int i = 1; i < nums.length; i++) {//数字被抵消，替换为下一个数字if (count == 0) {result = nums[i];count = 1;}else if (nums[i] == result) {//相等就++count++;}else{//不相同就--count--;}}//再次确认这个数组是否超过数组长度的一半count = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] == result) {count++;}}if (count > nums.length/2) {return result;}return 0;}

题目链接 数组中出现次数超过一半的数字