leetcode第347题前k个高频元素

题目描述:

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//定义结构体，记录数字及其出现的次数
struct Times{
    int num;
    int cnt;
};
//用于初始数组nums的排序
int cmp(const void* a,const void* b){
    return *(int*)a - *(int*)b;
}
//用于结构体的一级排序
int cmps(const void* a,const void* b){
    return (*(struct Times*)b).cnt - (*(struct Times*)a).cnt;
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    *returnSize = k;
    int* res = (int*)malloc(sizeof(int)*k);
    struct Times time[numsSize];
    int index=0;
    //1.对初始数组nums进行排序
    qsort(nums,numsSize,sizeof(int),cmp);
    //2.遍历计算各个数字出现的次数
    time[index].num = nums[0];
    time[index].cnt = 1;
    for(int i=1;i<numsSize;i++){
        if(nums[i]==nums[i-1])time[index].cnt++;
        else{
            time[++index].num = nums[i];
            time[index].cnt = 1;
        }
    }
    //3.对结构体数组按出现次数降序排序
    qsort(time,index+1,sizeof(struct Times),cmps);
    //4.返回前k个数字
    for(int i=0;i<k;i++){
        res[i] = time[i].num;
    }

    return res;
}


​

leetcode第169题多数元素

题目描述：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：nums = [3,2,3]
输出：3

示例 2：

1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2

与上面的那个题目类似，等同于上面那个元素中k=1的时候

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct Times{
    int num;
    int cnt;
};
int cmp(const void*a,const void*b){
    return (*(int*)a-*(int*)b);
}
int cmps(const void*a,const void*b){
    return (*(struct Times*)b).cnt-(*(struct Times*)a).cnt;
}


int majorityElement(int* nums, int numsSize) {
    struct Times time[numsSize];
    int index=0;
    qsort(nums,numsSize,sizeof(int),cmp);
    time[index].num=nums[0];
    time[index].cnt=1;
    for(int i=1;i<numsSize;i++){
        if(nums[i]==nums[i-1]){
            time[index].cnt++;
        }
        else{
            time[++index].num=nums[i];
            time[index].cnt=1;
        }
    }
    qsort(time,index+1,sizeof(struct Times),cmps);
    return time[0].num;
}

第169题更方便的题解:

摩尔投票算法(摩尔投票算法的基本思想是将众数与其他元素进行抵消，最终剩下的就是众数。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int majorityElement(int* nums, int numsSize) {
    int candidate = nums[0];
    int count = 1;

    // 进行摩尔投票
    for (int i = 1; i < numsSize; i++) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }

    // 验证 candidate 是否为众数
    count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate) {
            count++;
        }
    }

    if (count > numsSize / 2) {
        return candidate;
    }

    // 这里假设输入是非空的，并且总是存在多数元素，因此不会到达这一步
    return -1; // 此处可以根据实际情况返回任何值
}