昆明建设网站的公司,网站备案号官网,平面设计投稿平台,济南网站建设网站建设题目描述#xff1a;
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。示例 1#xff1a;输入#xff1a;nums [3,2,3]
输出
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3]
输出3
示例 2输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length
1 n 5 * 104
-109 nums[i] 109
算法先排序
思路
先排序再对相邻数进行比较记录次数取最大次数的值
代码实现
int cmp(const void *a,const void *b){return *(int *)a-*(int *)b;
}int majorityElement(int* nums, int numsSize) {qsort(nums,numsSize,sizeof(int),cmp);int cnt1;int i;int retnums[0];for(i0;inumsSize-1;i){//超过半数if(cntnumsSize/2) return ret;//未超过半数if(nums[i]!nums[i1]){//不等cnt1;//计数归零retnums[i1];//重设ret}else{//相等cnt;}}return ret;
}
算法抵消
思路
抵消次数以达到更新比较值的目的
代码实现
int majorityElement(int* nums, int numsSize) {int i0;int mostnums[i];int j1;//1 1 3 3 1 2 1 2 1 for( i1;inumsSize;i){if(nums[i]most) j;else{if(j0){mostnums[i];//重新开始比较j;}else j--;//抵消次数(比较剩余元素)}}return most;//返回最多元素
}
