leetcode697：数组的度（degree_of_an_array_697）

carloscn commented 1 year ago

问题描述

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入：nums = [1,2,2,3,1] 输出：2 解释：输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。连续子数组里面拥有相同度的有如下所示： [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。示例 2：

输入：nums = [1,2,2,3,1,4,2] 输出：6 解释：数组的度是 3 ，因为元素 2 重复出现 3 次。所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

提示：

nums.length 在 1 到 50,000 范围内。 nums[i] 是一个在 0 到 49,999 范围内的整数。

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/degree-of-an-array

carloscn commented 1 year ago

问题分析

static int32_t degree_array(const int64_t *array, size_t len, size_t *out)
{
    int32_t ret = 0;
    int64_t *buffer = NULL;
    size_t *index = NULL;
    size_t i = 0, j = 0;
    size_t ind = 0;
    size_t min_index = 0;
    int64_t e = 0;
    size_t count = 0;
    size_t max_count = 0;

    UTILS_CHECK_LEN(len);
    UTILS_CHECK_PTR(array);
    UTILS_CHECK_PTR(out);

    buffer = (int64_t *)calloc(sizeof(int64_t), len);
    UTILS_CHECK_PTR(buffer);
    memcpy(buffer, array, sizeof(int64_t) * len);

    index = (size_t *)calloc(sizeof(size_t), len);
    UTILS_CHECK_PTR(index);

    for (i = 0; i < len; i ++) {
        index[i] = i;
    }

    for (i = 0; i < len - 1; i ++) {
        for (j = 0; j < len - i - 1; j ++) {
            if (buffer[j] > buffer[j + 1]) {
                utils_swap_int64(buffer + j, buffer + j + 1);
                utils_swap_size_t(index + j, index + j + 1);
            }
        }
    }

    utils_print_int64_array(buffer, len, "the buffer:");
    utils_print_size_t_array(index, len, "index is  :");

    for (i = 0, j = 0; i < len - 1; i ++) {
        if (buffer[i] == buffer[i + 1]) {
            count ++;
            if (count >= 1 && count > max_count) {
                ind = utils_int64_abs(index[i + 1] - index[j]);
                min_index = ind > min_index ? ind : min_index;
                LOG("the min_index is %zu, ind = %zu\n", min_index, ind);
            } else if (count >= 1 && count == max_count) {
                ind = utils_int64_abs(index[i + 1] - index[j]);
                min_index = ind < min_index ? ind : min_index;
                LOG("the min_index is %zu, ind = %zu\n", min_index, ind);
            }
            max_count = count > max_count ? count : max_count;
        } else {
            count = 0;
            j = i + 1;
        }
    }

    *out = min_index + 1;

finish:
    UTILS_SAFE_FREE(buffer);
    UTILS_SAFE_FREE(index);
    return ret;
}

fn degree_array(vec: &[i64]) -> usize
{
    let mut count:usize = 0;
    let mut max_count:usize = 0;
    let mut ind:usize = 0;
    let mut min_index:usize = 0;
    let mut buffer:Vec<i64> = Vec::from(vec);
    let mut index:Vec<i64> = Vec::from(vec);
    let len:usize = vec.len();
    let mut i:usize = 0;
    let mut j:usize = 0;

    println!("the len is {len}");

    while i < len {
        index[i] = i as i64;
        i += 1;
    }

    for i in 0..len {
        for j in 0..len - 1 - i {
            if buffer[j] > buffer[j + 1] {
                println!("swap the index {j}, {}", j + 1);
                buffer.swap(j, j + 1);
                index.swap(j, j + 1);
            }
        }
    }

    println!("buffer is {:?}", buffer);
    println!("index  is {:?}", index);

    j = 0;
    for i in 0..len - 1 {
        if buffer[i] == buffer[i + 1] {
            count += 1;
            if (count >= 1) && (count > max_count) {
                ind = i64::abs((index[i + 1] as i64) - (index[j] as i64)) as usize;
                if (ind > min_index) {
                    min_index = ind;
                }
            } else if (count >= 1) && (count == max_count) {
                ind = i64::abs((index[i + 1] as i64) - (index[j] as i64)) as usize;
                if (ind < min_index) {
                    min_index = ind;
                }
            }
            if (count > max_count) {
                max_count = count;
            }
        } else {
            count = 0;
            j = i + 1;
        }
    }

    return min_index + 1;
}

carloscn commented 1 year ago

code

https://github.com/carloscn/structstudy/blob/master/c_programming/array/n42_degree_of_an_array_697.c https://github.com/carloscn/structstudy/blob/master/rust_programming/array/src/n42_degree_of_an_array_697.rs

carloscn / structstudy