【LeetCode每日一题】——1331.数组序号转换

这篇具有很好参考价值的文章主要介绍了【LeetCode每日一题】——1331.数组序号转换。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一【题目类别】

  • 排序

二【题目难度】

  • 简单

三【题目编号】

  • 1331.数组序号转换

四【题目描述】

  • 给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号。
  • 序号代表了一个元素有多大。序号编号的规则如下:
    • 序号从 1 开始编号。
    • 一个元素越大,那么序号越大。如果两个元素相等,那么它们的序号相同。
    • 每个数字的序号都应该尽可能地小。

五【题目示例】

  • 示例 1:

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

    • 输入:arr = [100,100,100]
    • 输出:[1,1,1]
    • 解释:所有元素有相同的序号。
  • 示例 3:

    • 输入:arr = [37,12,28,9,100,56,80,5,12]
    • 输出:[5,3,4,2,8,6,7,1,3]

六【题目提示】

  • 0 < = a r r . l e n g t h < = 1 0 5 0 <= arr.length <= 10^5 0<=arr.length<=105
  • − 1 0 9 < = a r r [ i ] < = 1 0 9 -10^9 <= arr[i] <= 10^9 109<=arr[i]<=109

七【解题思路】

  • 利用排序+哈希
  • 首先复制一份原数组,然后对原数组从小到大排序
  • 然后对排序后的数组进行哈希,key为数组值,val为数组值对应的排序,这样就可以对数组值去重,且记录每个数组值对应的数组下标
  • 最后遍历复制的数组,对于每个元素我们取出其排序后的位置,设置为当前值
  • 最后返回复制的数组即可

八【时间频度】

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn) n n n为传入的数组的长度
  • 空间复杂度: O ( n ) O(n) O(n) n n n为传入的数组的长度

九【代码实现】

  1. Java语言版
class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        int[] temp = new int[n];
        for(int i = 0;i < n;i++){
            temp[i] = arr[i];
        }
        Arrays.sort(arr);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(!map.containsKey(arr[i])){
                map.put(arr[i], map.size() + 1);
            }
        }
        for(int i = 0;i < n;i++){
            temp[i] = map.get(temp[i]);
        }
        return temp;
    }
}
  1. C语言版
typedef struct
{
    int key;
    int val;
    UT_hash_handle hh;
}HashItem;

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int* arrayRankTransform(int* arr, int arrSize, int* returnSize)
{
    int* sortArr = (int*)malloc(sizeof(int) * arrSize);
    int* res = (int*)malloc(sizeof(int) * arrSize);
    memcpy(sortArr, arr, sizeof(int) * arrSize);
    qsort(sortArr, arrSize, sizeof(int), cmp);
    HashItem *map = NULL;
    for(int i = 0;i < arrSize;i++)
    {
        HashItem *temp = NULL;
        HASH_FIND_INT(map, &sortArr[i], temp);
        if(temp == NULL)
        {
            temp = (HashItem *)malloc(sizeof(HashItem));
            temp->key = sortArr[i];
            temp->val = HASH_COUNT(map) + 1;
            HASH_ADD_INT(map, key, temp);
        }
    }
    for(int i = 0;i < arrSize;i++)
    {
        HashItem *temp = NULL;
        HASH_FIND_INT(map, &arr[i], temp);
        res[i] = temp->val;
    }
    *returnSize = arrSize;
    HashItem *cur, *temp;
    HASH_ITER(hh, map, cur, temp)
    {
        HASH_DEL(map, cur);
        free(cur);
    }
    free(sortArr);
    return res;
}
  1. Python语言版
class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        n = len(arr)
        temp = [0] * n
        for i in range(0, n):
            temp[i] = arr[i]
        arr.sort()
        map = {}
        for i in range(0, n):
            if arr[i] not in map:
                map[arr[i]] = len(map) + 1
        for i in range(0, n):
            temp[i] = map[temp[i]]
        return temp
  1. C++语言版
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        int n = arr.size();
        vector<int> temp = arr;
        sort(arr.begin(), arr.end());
        unordered_map<int, int> map;
        for(int i = 0;i < n;i++){
            if(!map.count(arr[i])){
                map[arr[i]] = map.size() + 1;
            }
        }
        for(int i = 0;i < n;i++){
            temp[i] = map[temp[i]];
        }
        return temp;
    }
};

十【提交结果】

  1. Java语言版
    【LeetCode每日一题】——1331.数组序号转换,LeetCode,算法,数据结构,LeetCode,排序,哈希表

  2. C语言版
    【LeetCode每日一题】——1331.数组序号转换,LeetCode,算法,数据结构,LeetCode,排序,哈希表

  3. Python语言版
    【LeetCode每日一题】——1331.数组序号转换,LeetCode,算法,数据结构,LeetCode,排序,哈希表

  4. C++语言版
    【LeetCode每日一题】——1331.数组序号转换,LeetCode,算法,数据结构,LeetCode,排序,哈希表文章来源地址https://www.toymoban.com/news/detail-654566.html

到了这里,关于【LeetCode每日一题】——1331.数组序号转换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ( 数组和矩阵) 697. 数组的度 ——【Leetcode每日一题】

    难度:简单 给定一个非空且只包含非负数的整数数组 nums ,数组的 度 的定义是指数组里任一元素出现频数的最大值。 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。 示例 1: 输入:nums = [1,2,2,3,1] 输出:2 解释: 输入数组的度是 2 ,因为

    2024年02月02日
    浏览(41)
  • Leetcode每日一题——“合并两个有序数组”

    各位CSDN的uu们你们好呀,又到小雅兰的愉快题解时候啦,今天,我们的题目内容是合并两个有序数组,下面,让我们进入合并两个有序数组的世界吧 示例 1: 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [ 1,2

    2023年04月24日
    浏览(64)
  • ( 数组) 209. 长度最小的子数组——【Leetcode每日一题】

    难度:中等 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

    2024年02月06日
    浏览(39)
  • LeetCode每日一题【977. 有序数组的平方】

    题目: 思路: 直接每个元素平方,然后排序,比较简单 双指针,一头一尾,每次比较头指针元素平方与尾指针元素平方的大小,若头指针的元素平方比较大,则头指针往后移动,否则尾指针往前移动

    2024年02月20日
    浏览(31)
  • ( 数组) 27. 移除元素 ——【Leetcode每日一题】

    难度:简单 给你一个数组 nums 和一个值 val ,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明

    2024年02月08日
    浏览(438)
  • 【LeetCode每日一题】53. 最大子数组和

    https://leetcode.cn/problems/maximum-subarray/description/ 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 先算出数组的前缀和,然后通过2个for循环遍历出所有的连续子数组。 寻找一个具有

    2024年02月04日
    浏览(51)
  • ( 数组和矩阵) 566. 重塑矩阵 ——【Leetcode每日一题】

    难度:简单 在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同( r x c )的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后的矩阵需要

    2024年02月07日
    浏览(39)
  • ( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】

    难度:简单 集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了集合 S 发生错误后的结果。 请你找出重复出现的整数,再找到

    2024年02月04日
    浏览(36)
  • 【LeetCode每日一题】410. 分割数组的最大值

    2024-1-21 410. 分割数组的最大值 思路:二分查找+贪心 利用二分查找法和贪心算法来求解将数组分割为m个非空连续子数组,使得每个子数组的和的最大值最小 首先,我们需要确定二分查找的左右边界。左边界 left 初始化为数组中的最大值,右边界 right 初始化为数组所有元素的

    2024年01月23日
    浏览(38)
  • 2023-08-13 LeetCode每日一题(合并两个有序数组)

    点击跳转到题目位置 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 **注意:**最终,合并后数组不应由函数返回,而是存储在数组 num

    2024年02月13日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包