leetcode2465: Number of Distinct Averages

carloscn commented 1 year ago

Description

You are given a 0-indexed integer array nums of even length.

As long as nums is not empty, you must repetitively:

Find the minimum number in nums and remove it. Find the maximum number in nums and remove it. Calculate the average of the two removed numbers. The average of two numbers a and b is (a + b) / 2.

For example, the average of 2 and 3 is (2 + 3) / 2 = 2.5. Return the number of distinct averages calculated using the above process.

Note that when there is a tie for a minimum or maximum number, any can be removed.

Example 1:

Input: nums = [4,1,4,0,3,5] Output: 2 Explanation:

Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = [4,1,4,3].
Remove 1 and 4. The average is (1 + 4) / 2 = 2.5, and nums = [4,3].
Remove 3 and 4, and the average is (3 + 4) / 2 = 3.5. Since there are 2 distinct numbers among 2.5, 2.5, and 3.5, we return 2.

Example 2:

Input: nums = [1,100] Output: 1 Explanation: There is only one average to be calculated after removing 1 and 100, so we return 1.

Constraints:

2 <= nums.length <= 100 nums.length is even. 0 <= nums[i] <= 100

carloscn commented 1 year ago

Description

static int32_t distinct_averages(int64_t *nums, size_t nums_size)
{
    int32_t ret = 0;
    float *rom = NULL;
    BUFFER_T *buffer = NULL;

    UTILS_CHECK_PTR(nums);
    UTILS_CHECK_LEN(nums_size);

    size_t rom_index = 0;
    rom = (float *)calloc(nums_size, sizeof(float));
    UTILS_CHECK_PTR(rom);

    buffer = buffer_malloc(nums_size);
    UTILS_CHECK_PTR(buffer);

    ret = buffer_append_array(buffer, nums, nums_size);
    UTILS_CHECK_RET(ret);
    do {
        size_t max_index, min_index;
        int64_t max_value, min_value;
        ret = buffer_get_max_value(buffer, &max_index, &max_value) || \
              buffer_remove(buffer, max_index, NULL);
        UTILS_CHECK_RET(ret);
        ret = buffer_get_min_value(buffer, &min_index, &min_value) || \
              buffer_remove(buffer, min_index, NULL);
        UTILS_CHECK_RET(ret);
        rom[rom_index ++] = ((float)max_value + (float)min_value) / 2.0f;
    } while (buffer_get_current_len(buffer) != 0);

finish:
    UTILS_SAFE_FREE(rom);
    buffer_free(buffer);
    return ret;
}

carloscn commented 1 year ago

Code

https://review.gerrithub.io/c/carloscn/structstudy/+/1171259 https://github.com/carloscn/structstudy/commit/9bb2055083fd060529c4e056b7befbe680581668

carloscn / structstudy