leetcode1331：数组序号转换（rank-transform-of-an-array）

[carloscn]

问题描述

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

序号从 1 开始编号。 一个元素越大，那么序号越大。不存在相同的元素！ 每个数字的序号都应该尽可能地小。  

示例 1：

输入：arr = [40,10,20,30] 输出：[4,1,2,3] 解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

提示：

0 <= arr.length <= 105 -109 <= arr[i] <= 109

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

[carloscn]

问题分析

pub fn array_rank_transform(arr: Vec<i32>) -> Vec<i32>
{
    if arr.len() < 1 {
        return arr;
    }

    let mut ret:Vec<i32> = vec![0;arr.len()];
    let mut temp = ret.clone();
    let mut n:usize = 0;

    while n < arr.len() {
        temp[n] = n as i32 + 1;
        n += 1;
    }

    let mut dup_vec = arr.clone();

    for i in 0..arr.len() - 1 {
        for j in 0..arr.len() - i - 1 {
            if dup_vec[j] > dup_vec[j + 1] {
                let mut t = dup_vec[j + 1];
                dup_vec[j + 1] = dup_vec[j];
                dup_vec[j] = t;
                t = temp[j + 1];
                temp[j + 1] = temp[j];
                temp[j] = t;
            }
        }
    }

    for i in 0..arr.len() {
        ret[temp[i] as usize - 1] = i as i32 + 1;
    }

    return ret;
}

[carloscn]

code

https://review.gerrithub.io/c/carloscn/structstudy/+/553526 https://github.com/carloscn/structstudy/commit/18e3c4634d98b251caef3b11351fccd7de4e6d2a

[carloscn]

存在相同元素的情况

使用hash表

use std::collections::HashMap;

pub fn array_rank_transform(arr: Vec<i32>) -> Vec<i32>
{
    if arr.len() < 1 {
        return arr;
    }

    let mut dup_vec = arr.clone();
    for i in 0..arr.len() - 1 {
        for j in 0..arr.len() - i - 1 {
            if dup_vec[j] > dup_vec[j + 1] {
                let t = dup_vec[j + 1];
                dup_vec[j + 1] = dup_vec[j];
                dup_vec[j] = t;
            }
        }
    }

    let mut n:usize = 0;
    let mut m:usize = 0;
    let mut hash:HashMap<i32, usize> = HashMap::new();
    while n < arr.len() {
        if !hash.contains_key(&dup_vec[n]) {
            hash.insert(dup_vec[n], m + 1);
            m += 1;
        }
        n += 1;
    }

    let mut ret:Vec<i32> = vec![0;arr.len()];
    for i in 0..arr.len() {
        ret[i] = (*hash.get(&arr[i]).unwrap()) as i32;
    }

    return ret;
}

[carloscn]

code

https://review.gerrithub.io/c/carloscn/structstudy/+/553551 https://github.com/carloscn/structstudy/commit/6e0d0398d319b6fc8b962c63a72f51f1f35b4db2