力扣——数组序号转换思路分析

101 阅读 0 评论 67 点赞

我是靠谱客的博主隐形大神，这篇文章主要介绍力扣——数组序号转换思路分析，现在分享给大家，希望可以做个参考。

题目：
给你一个整数数组 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]

解题思路1：首先阅读题目，我觉得这应该是一个很简单的排序问题，我们只需要过滤掉原数组当中的重复元素，然后将其余元素进行排序，然后把原数组遍历每个元素在排序列表中的位置，再进行对照序号赋值，就能得出正确答案，于是我就按照这个思路开始编写算法了。
所遇问题1：虽然这个算法解题思路很清晰，但是因为算法效率太低，计算时间太长，卡在了最后一个测试案例上，最终以失败告终。

复制代码

package 力扣;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 数组序号转换 {
    public static void main(String[] args) {
        int[] arr = {2,-11,24,15,26,-31,-48,-49,22,37,-36};
        arrayRankTransform(arr);
    }
    public static int[] arrayRankTransform(int[] arr) {
        ArrayList list = new ArrayList();
        int s = arr.length;
        //1.用于过滤重复数组元素
        for (int i = 0; i < s; i++) {
            if (!list.contains(arr[i])){
                list.add(arr[i]);
            }
        }
        int temp = list.size();
        //2.转为数组之后进行排序
        Object[] brr = list.toArray();
        Arrays.sort(brr);
        //3.对于原数组遍历寻找在排序位置的值然后标记
        for (int i = 0; i < s; i++) {
            for (int j = 0; j < temp; j++) {
                if (arr[i] == (int)brr[j]){
                    arr[i] = j+1;
                    break;
                }
            }
        }
        //4.输出相应的值（提交代码时请删掉）
        for (int i = 0; i < s; i++) {
            System.out.print(arr[i]+",");
        }
        return arr;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package 力扣;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;



public class 数组序号转换 {
    public static void main(String[] args) {
        int[] arr = {2,-11,24,15,26,-31,-48,-49,22,37,-36};
        arrayRankTransform(arr);
    }
    public static int[] arrayRankTransform(int[] arr) {
        ArrayList list = new ArrayList();
        int s = arr.length;
        //1.用于过滤重复数组元素
        for (int i = 0; i < s; i++) {
            if (!list.contains(arr[i])){
                list.add(arr[i]);
            }
        }
        int temp = list.size();
        //2.转为数组之后进行排序
        Object[] brr = list.toArray();
        Arrays.sort(brr);
        //3.对于原数组遍历寻找在排序位置的值然后标记
        for (int i = 0; i < s; i++) {
            for (int j = 0; j < temp; j++) {
                if (arr[i] == (int)brr[j]){
                    arr[i] = j+1;
                    break;
                }
            }
        }
        //4.输出相应的值（提交代码时请删掉）
        for (int i = 0; i < s; i++) {
            System.out.print(arr[i]+",");
        }
        return arr;
    }
}

解题思路2：通过对于第一个算法经验总结，我觉得应该换一种思路来解决问题，于是我思考能不能用一个二维数组分别来记录原数组的值和序号，先以原数组元素值大小进行排序，然后将元素值替换成他们现在的位序，最后再以原数组值的原本位序进行排序，这样就能按顺序得出每一个元素在排序列中的编号，优化了第一种算法当中排序完之后一一对照遍历查找的低效率。
所遇问题2：首先在这个算法当中，我卡在了[ ]空数组的测试值当中，会因为数组越界而报错，所以我添加了对数组长度判断而进行的两种情况，但是最后还是因为算法超时，效率过低而以失败告终。

复制代码

package 力扣;
import java.util.Arrays;

public class 数组序号转换优化 {
    public static void main(String[] args) {
        int[] arr = {19,22,-47,24,-37};
        arr = arrayRankTransform(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public static int[] arrayRankTransform(int[] arr) {
        int s = arr.length;
        if (s != 0){
            int[][] brr = new int[2][s];
            int add = 1;
            int i = 0,j = 0;
            //1.用二维数组来存储一维数组，第二层表示序号
            for (i = 0; i < s; i++) {
                brr[0][i] = arr[i];
                brr[1][i] = add++;
            }
            //比较数字
            int temp = 0;
            //下标记录
            int flag = 0;
            //2.先以原数组进行排序
            for (i = 0; i < s-1; i++) {
                temp = brr[0][i];
                flag = i;
                for (j = i; j < s; j++) {
                    if(brr[0][j] < temp){
                        temp = brr[0][j];
                        flag = j;
                    }
                }
                int temp1 = brr[0][i];
                int temp2 = brr[1][i];
                brr[0][i] = brr[0][flag];
                brr[1][i] = brr[1][flag];
                brr[0][flag] = temp1;
                brr[1][flag] = temp2;
            }
            //3.进行位序替换
            add = 1;
            temp = brr[0][0];
            brr[0][0] = add;
            for (int k = 1; k < s; k++) {
                if(brr[0][k] != temp){
                    temp = brr[0][k];
                    brr[0][k] = ++add;
                }else{
                    brr[0][k] = add;
                }
            }
            //4.再以序号原数组进行排序
            for (i = 0; i < s-1; i++) {
                temp = brr[1][i];
                flag = i;
                for (j = i; j < s; j++) {
                    if(brr[1][j] < temp){
                        temp = brr[1][j];
                        flag = j;
                    }
                }
                if(flag != i){
                    int temp1 = brr[0][i];
                    int temp2 = brr[1][i];
                    brr[0][i] = brr[0][flag];
                    brr[1][i] = brr[1][flag];
                    brr[0][flag] = temp1;
                    brr[1][flag] = temp2;
                }
            }
            return brr[0];
        }
        else{
            return arr;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package 力扣;
import java.util.Arrays;

public class 数组序号转换优化 {
    public static void main(String[] args) {
        int[] arr = {19,22,-47,24,-37};
        arr = arrayRankTransform(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public static int[] arrayRankTransform(int[] arr) {
        int s = arr.length;
        if (s != 0){
            int[][] brr = new int[2][s];
            int add = 1;
            int i = 0,j = 0;
            //1.用二维数组来存储一维数组，第二层表示序号
            for (i = 0; i < s; i++) {
                brr[0][i] = arr[i];
                brr[1][i] = add++;
            }
            //比较数字
            int temp = 0;
            //下标记录
            int flag = 0;
            //2.先以原数组进行排序
            for (i = 0; i < s-1; i++) {
                temp = brr[0][i];
                flag = i;
                for (j = i; j < s; j++) {
                    if(brr[0][j] < temp){
                        temp = brr[0][j];
                        flag = j;
                    }
                }
                int temp1 = brr[0][i];
                int temp2 = brr[1][i];
                brr[0][i] = brr[0][flag];
                brr[1][i] = brr[1][flag];
                brr[0][flag] = temp1;
                brr[1][flag] = temp2;
            }
            //3.进行位序替换
            add = 1;
            temp = brr[0][0];
            brr[0][0] = add;
            for (int k = 1; k < s; k++) {
                if(brr[0][k] != temp){
                    temp = brr[0][k];
                    brr[0][k] = ++add;
                }else{
                    brr[0][k] = add;
                }
            }
            //4.再以序号原数组进行排序
            for (i = 0; i < s-1; i++) {
                temp = brr[1][i];
                flag = i;
                for (j = i; j < s; j++) {
                    if(brr[1][j] < temp){
                        temp = brr[1][j];
                        flag = j;
                    }
                }
                if(flag != i){
                    int temp1 = brr[0][i];
                    int temp2 = brr[1][i];
                    brr[0][i] = brr[0][flag];
                    brr[1][i] = brr[1][flag];
                    brr[0][flag] = temp1;
                    brr[1][flag] = temp2;
                }
            }
            return brr[0];
        }
        else{
            return arr;
        }
    }
}

解题思路3：最后我在浏览解题评论区当中发现了超级优化的解题思路，原作者是这样解释他的思路的：代码详解
在这里插入图片描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

    public static int[] arrayRankTransform(int[] arr) {
        //分别设置最大无穷和最小无穷
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    //分别找出数组中最小和最大值存入min和max当中
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
    //创建数组，容量为最大值减去最小值+1
        int[] count = new int[max - min + 1];
    //遍历数组，在原数组每项值减去最小值的位置处赋值1
        for (int num : arr)
            count[num - min] = 1;
    //创建数组，容量为最大值减去最小值+2
        int[] preSum = new int[count.length + 1];
    //遍历preSum数组，将每个位置赋值是preSum[i - 1] + count[i - 1]
        for (int i = 1; i < preSum.length; i++)
            preSum[i] = preSum[i - 1] + count[i - 1];
    //创建数组，容量为原数组长度
        int[] ans = new int[arr.length];
        int index = 0;
        for (int num : arr)
            ans[index++] = preSum[num - min] + 1;
        return ans;
    }

代码理解：作者的这个代码确实十分简洁精炼，但是理解起来却显得有些吃力，我对作者的代码添加上注释，然后逐句分析，有了自己的理解，首先作者想要利用桶排序算法来对于庞大的数组进行排序以提高效率，我还特意去查看了这个排序算法，整体思路就是对于无序数组，按范围拆分进行入桶操作，然后再在桶中进行排序后再拼接。

首先的关键在于我们要先知道如何定制桶范围的大小，即确定数组中的大和最小值。
然后创建桶，我们确保每个桶中的元素只有一个，这样就相当递归算法求解到了最后的出口，作者想到的是用数组中每一个值减去最小值的数字作为桶的标志，然后在创建的count 数组中给他赋值1。
由于数字越大，它减去最小值得到的值也越大，所以上述操作相当于是给数组排序了，然后preSum 数组的作用是将桶中零碎的数字拼接起来，由于操作2全部赋值了1，我们并不知道每个数字实际排在第几位，这时候我们只需要将每位数字累加，这样越靠后的值累加起来也就越大，而且每次加一，我们就能清晰的知道每个元素的位序了。
做完以上操作，我们只需要再创建一个和原数组长度相同的数组，再利用值减去最小值得方法，去相应的位置找到对应的位序值，给他存入保存。

学习收获：

想要将数组去重，可以利用ArrayList

复制代码

1
2
3
4
5
6
7
8
9
 ArrayList list = new ArrayList();
        int s = arr.length;
        //1.用于过滤重复数组元素
        for (int i = 0; i < s; i++) {
            if (!list.contains(arr[i])){
                list.add(arr[i]);
            }
        }

想要获取无穷最小和无穷最大

复制代码

1
2
3
 //分别设置最大无穷和最小无穷
 int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

最后

以上就是隐形大神最近收集整理的关于力扣——数组序号转换思路分析的全部内容，更多相关力扣——数组序号转换思路分析内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Leecode
浏览次数：101 次浏览
发布日期：2023-10-03 06:51:25
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzogf1_14__23_k1.html

力扣——数组序号转换思路分析

最后

评论列表共有 0 条评论

发表评论取消回复

力扣——数组序号转换思路分析

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复