美文网首页
【算法题】2191. 将杂乱无章的数字排序

【算法题】2191. 将杂乱无章的数字排序

作者: 程序员小2 | 来源:发表于2023-03-21 21:32 被阅读0次

题目:

给你一个下标从 0 开始的整数数组 mapping ,它表示一个十进制数的映射规则,mapping[i] = j 表示这个规则下将数位 i 映射为数位 j 。

一个整数 映射后的值 为将原数字每一个数位 i (0 <= i <= 9)映射为 mapping[i] 。

另外给你一个整数数组 nums ,请你将数组 nums 中每个数按照它们映射后对应数字非递减顺序排序后返回。

注意:

如果两个数字映射后对应的数字大小相同,则将它们按照输入中的 相对顺序 排序。
nums 中的元素只有在排序的时候需要按照映射后的值进行比较,返回的值应该是输入的元素本身。

示例 1:

输入:mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
输出:[338,38,991]
解释:
将数字 991 按照如下规则映射:

  1. mapping[9] = 6 ,所有数位 9 都会变成 6 。
  2. mapping[1] = 9 ,所有数位 1 都会变成 8 。
    所以,991 映射的值为 669 。
    338 映射为 007 ,去掉前导 0 后得到 7 。
    38 映射为 07 ,去掉前导 0 后得到 7 。
    由于 338 和 38 映射后的值相同,所以它们的前后顺序保留原数组中的相对位置关系,338 在 38 的前面。
    所以,排序后的数组为 [338,38,991] 。
    示例 2:

输入:mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
输出:[123,456,789]
解释:789 映射为 789 ,456 映射为 456 ,123 映射为 123 。所以排序后数组为 [123,456,789] 。

提示:

mapping.length == 10
0 <= mapping[i] <= 9
mapping[i] 的值 互不相同 。
1 <= nums.length <= 3 * 10^4
0 <= nums[i] < 10^9

java代码:

class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        //二维数组,copy[i][0]:保存数据的映射,copy[i][1]:保存数据的映射nums[i]
        
        int[][] copy=new int[nums.length][2];
        
        for (int i = 0; i < copy.length; i++) {
            copy[i][0]=nums[i];
            copy[i][1]=nums[i];
        }
        //对数据进行映射
        for (int i = 0; i < copy.length; i++) {
            Stack<Integer> stack=new Stack<>();
            if(copy[i][0]==0) stack.push(0);
            int tmp=0;
            while (copy[i][0]>0) {
                tmp=copy[i][0]%10;
                stack.push(tmp);
                copy[i][0]/=10;
            }
            tmp=0;
            while (!stack.isEmpty()) {
                tmp*=10;
                tmp+=mapping[stack.pop()];
            }
            copy[i][0]=tmp;
        }
        //排序
        Arrays.sort(copy,new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        
        for (int i = 0; i < copy.length; i++) {
            nums[i]=copy[i][1];
        }
        
        return nums;
    }
}

相关文章

  • 排序算法总结

    一、概述 排序算法概念 在计算机科学与数学中,一个排序算法是将一组杂乱无章的数据按一定的规律顺次排列起来的算法。排...

  • 2020-11-24 算法

    选择排序算法 冒泡排序算法 原理:数字两两进行比较,将大的值移动到右侧,继续进行比较直到最大值移动到最右侧,则完成...

  • 冒泡排序

    冒泡排序是一种常见的排序算法,本题要求用冒泡排序算法对一组数字进行从小到大排序 输入:输入的是一行数字,就是我们需...

  • python笔试面试项目实战2020百练6归并排序快速排序

    归并排序 现在,我们将注意⼒转向使⽤分治策略改进排序算法。要研究的第⼀个算法是归并排序 ,它是递归算法,每次将⼀个...

  • 插入排序

    插入排序 # 目标:将数组从低到高(或从高到低)排序。 您将获得一系列数字,需要按正确的顺序排列。插入排序算法的工...

  • golang实现堆排序

    算法题:给定一个整型数组,将数组的中的元素按升序排序。 基本思路:操作:排序输入:无序整型数组输出:有序整型数组 ...

  • 排序算法介绍和分类

    排序算法的介绍 排序也称排序算法(Sort Alogorithm),排序是将一组数据,依指定的顺序进行排序的过程 ...

  • JS基础回顾:sort

    排序算法 排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小。如果是数字...

  • 【20-3】sorted

    排序算法 排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小。如果是数字...

  • 排序:(一)排序算法小常识

    1 算法稳定性 算法稳定性的意义 如果只是简单的进行数字的排序,那么稳定性将毫无意义。如果排序的内容仅仅是一个复杂...

网友评论

      本文标题:【算法题】2191. 将杂乱无章的数字排序

      本文链接:https://www.haomeiwen.com/subject/zutvrdtx.html