leetcode506：相对名次（relative-ranks）

carloscn commented 1 year ago

问题描述

给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都互不相同。

运动员将根据得分决定名次，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

名次第 1 的运动员获金牌 "Gold Medal" 。名次第 2 的运动员获银牌 "Silver Medal" 。名次第 3 的运动员获铜牌 "Bronze Medal" 。从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

示例 1：

输入：score = [5,4,3,2,1] 输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"] 解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2：输入：score = [10,3,8,9,4] 输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"] 解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。

提示：

n == score.length 1 <= n <= 104 0 <= score[i] <= 106 score 中的所有值互不相同

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/relative-ranks

carloscn commented 1 year ago

问题分析

使用冒泡排序对数组进行排序，接着设定一个跟随向量index，排序数组根据index一起变动。然后根据index的值进行名次的生成。

static const char *first_str = "Gold Medal";
static const char *sec_str = "Silver Medal";
static const char *third_str = "Bronze Medal";

static int32_t relative_rank(int32_t *array, size_t len)
{
    int32_t ret = 0;
    size_t i = 0, j = 0;
    int32_t max = 0;
    int32_t *index = NULL;
    char *strlist[100] = { NULL };
    char temp[3] = {0};

    UTILS_CHECK_PTR(array);
    UTILS_CHECK_LEN(len);

    index = (int32_t *)malloc(sizeof(int32_t) * len);
    UTILS_CHECK_PTR(index);

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

    for (j = 0; j < len - 1; j ++) {
        for (i = 0; i < len - j - 1; i ++) {
            if (array[i] < array[i + 1]) {
                utils_swap_int32(&array[i], &array[i + 1]);
                utils_swap_int32(&index[i], &index[i + 1]);
            }
        }
    }
    utils_print_int32_array(index, len, "the reorder index : ");

    for (i = 0; i < len; i ++) {
        if (index[i] == 0) {
            strlist[i] = strdup(first_str);
        } else if (index[i] == 1) {
            strlist[i] = strdup(sec_str);
        } else if (index[i] == 2) {
            strlist[i] = strdup(third_str);
        } else {
            sprintf(temp, "%d", index[i] + 1);
            strlist[i] = strdup(temp);
        }
    }
    LOG("output : \n");
    for (i = 0; i < len; i ++) {
        printf("%s, ", strlist[i]);
        free(strlist[i]);
    }
    printf("\n");

finish:
    if (index != NULL)
        free(index);
    return ret;
}

carloscn commented 1 year ago

code

https://github.com/carloscn/structstudy/blob/master/c_programming/array/38_relative-ranks_506.c

carloscn / structstudy