leetcode169：多数元素（majority-element）

carloscn commented 2 years ago

给定一个大小为 n 的数组 nums ，返回其中的多数元素。（改造一下原题，只是最多的元素）

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

示例 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 来源：力扣（LeetCode）链接：https://leetcode.cn/problems/majority-element

carloscn commented 2 years ago

问题分析：

leetcode原题应该是使用摩尔投票法完整：数组中次数出现超过一半的数字（摩尔投票法）本题进行改造，改造成为只查找多个元素。比如[1,1,2,2,3,3,4,4,5,5,5] 这里5最多，但是没有超过n/2。我们使用最朴素的方法，每个元素计数然后统计出最大的数字之后返回结果：

static int32_t majority_element(const int64_t *array, size_t array_size, int64_t *out)
{
    int32_t ret = 0;
    size_t i = 0, j = 0;
    size_t count = 0, max_count = 0;
    int64_t target = 0;

    UTILS_CHECK_PTR(array);
    UTILS_CHECK_PTR(out);

    if (0 == array_size)
        goto finish;

    for (i = 0; i < array_size; i ++) {
        target = array[i];
        for (j = i + 1; j < array_size; j ++) {
            if (target == array[j]) {
                max_count = (++count >= max_count) ?    \
                            (*out = target, count) : max_count;
            }
        }
    }

finish:
    return ret;
}

carloscn commented 2 years ago

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/array/18_majority-element_169.c

carloscn / structstudy

leetcode169：多数元素（majority-element） #54

问题分析：

code:

result: