给定一个大小为 n
的数组 nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋
的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
int majorityElement(int* nums, int numsSize) {
int max = numsSize / 2;
if(numsSize<2){
return nums[0];
}
for (int i = 0; i < (numsSize+1) / 2; i++) {
int count = 0;
for (int j = 0; j < numsSize; j++) {
if (nums[i] == nums[j]) {
count++;
}
if (count > max)
return nums[i];
}
}
return 0;
}
超出时间范围了
只好优化
冒泡排序,中间那个元素
int majorityElement(int* nums, int numsSize) {
if(numsSize==1||numsSize==2){
return nums[0];
}
for (int i = 0; i < numsSize - 1; i++) {
for (int j = 0; j < numsSize - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums[numsSize / 2 ];
}
还是超出时间范围了
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}