java—有没有简单的方法可以在排序数组后保留原始索引而不使用比较器？

wvmv3b1j 于 2021-08-20 发布在 Java

关注(0)|答案(3)|浏览(403)

我实现了一个数组，其中一个数组的索引为零。考虑下面的数组：

Array :             X S T U A C D B F H 
Index :             0 1 2 3 4 5 6 7 8 9
After sorting this array : 
Array :             A B C D F H S T U X
Index :             0 1 2 3 4 5 6 7 8 9
Original indices :  4 7 5 6 8 9 1 2 3 0

早期的a位于索引4，但在排序数组中，它位于索引0，其他值也是如此。程序的预期输出表示为原始索引。我不想打印排序数组中的元素，而是希望在排序后打印它们的原始索引。
虽然这段代码工作正常，但我想知道是否有其他简单的技术可以用来保留原始数组索引，而不必使用比较器。这里的想法是保留索引，因此我使用comparator：
在这个比较器中，我保留了要排序的实际数组。另外，如果您注意到，compare方法会根据提供给它的索引来比较实际数组的值。这里的关键是提供索引，而不是要排序的实际值。
s是要排序的字符数组，indexarray是辅助数组。排序之前，索引数组将以0–要排序的数组长度的顺序包含数字。当我在索引数组上调用arrays.sort方法时，它将两个索引传递给compare方法，并比较存储在这些索引中的值。

```public class ArrayIndexComparator implements Comparator<Integer>
    {
        private final Character[] A;
        public ArrayIndexComparator(Character[] arr)
        {
            this.A = arr;
        }

        public int compare(Integer o1, Integer o2)
        {
            return A[o1].compareTo(A[o2]);
        }
    }```
 ```public static void main(String[] args)
    {
        Character[] S = new Character[]{'X','S','T','U','A','C','D','B','F','H'};
        Integer[] indexArray = new Integer[S.length];
        IntStream.range(0, S.length).forEach(val -> indexArray[val] = val);
        ArrayIndexComparator comp = new ArrayIndexComparator(S);
        Arrays.sort(indexArray, comp);
        System.out.println(Arrays.toString(indexArray));
    }```

Java performance Arrays sorting java-8

来源：https://stackoverflow.com/questions/68321245/is-there-any-simple-way-to-preserve-original-indices-after-sorting-array-without

3条答案

按热度按时间

v9tzhpje1#

你可以这样做。

String[] arr =
        { "X", "S", "T", "U", "A", "C", "D", "B", "F", "H" };

根据字符串对索引进行排序

int[] intArray = IntStream.range(0, arr.length).boxed()
        .sorted(Comparator.comparing(i -> arr[i]))
        .mapToInt(Integer::intValue).toArray();
System.out.println(Arrays.toString(intArray));

然后使用 Arrays.setAll 构造已排序的字符数组。

String[] newArr = new String[arr.length];
Arrays.setAll(newArr,i->arr[intArray[i]]);
System.out.println(Arrays.toString(newArr));

印刷品

[4, 7, 5, 6, 8, 9, 1, 2, 3, 0]
[A, B, C, D, F, H, S, T, U, X]

赞(0）回复(0）举报 2021-08-20

r6l8ljro2#

至少有两种方法可以避免使用自定义项 Comparator 按索引而不是值排序，但它们并不简单，我强烈建议不要使用它们——我在这里介绍这个主题是出于兴趣。
第一个想法是创建一个结合原始值的代理值 Character 值及其索引，例如，将该值乘以数组的长度 n 并添加索引。在此代理项值上排序后，通过
mod n 获取索引。

Character[] s = new Character[]{'X','S','T','U','A','C','D','B','F','H'};

int n = s.length;

Integer[] idx = new Integer[s.length];
for(int i=0; i<s.length; i++) idx[i] = s[i]*n + i;

System.out.println(Arrays.toString(idx));

Collections.sort(Arrays.asList(idx));

System.out.println(Arrays.toString(idx));

for(int i=0; i<s.length; i++) idx[i] %= n;

System.out.println(Arrays.toString(idx));

输出：

[880, 831, 842, 853, 654, 675, 686, 667, 708, 729]
[654, 667, 675, 686, 708, 729, 831, 842, 853, 880]
[4, 7, 5, 6, 8, 9, 1, 2, 3, 0]

这里明显的问题是在大数组和/或字符的情况下出现溢出。
另一个选项是使用Map存储字符的原始位置，并在对原始数组排序后执行查找。

Character[] s = new Character[]{'X','S','T','U','A','C','D','B','F','H'};

Map<Character,Integer> map = new HashMap<>();
for(int i=0; i<s.length; i++) map.put(s[i], i);

System.out.println(map);

Collections.sort(Arrays.asList(s));

Integer[] idx = new Integer[s.length];
for(int i=0; i<s.length; i++)idx[i] = map.get(s[i]);

System.out.println(Arrays.toString(idx));

输出：

{A=4, B=7, C=5, S=1, D=6, T=2, U=3, F=8, H=9, X=0}
[4, 7, 5, 6, 8, 9, 1, 2, 3, 0]

这里的问题是不允许重复。

赞(0）回复(0）举报 2021-08-20

92vpleto3#

使用comparator.comparating可以更轻松地定义比较器。

Comparator<Integer> comp = Comparator.comparing(i -> S[i]);

赞(0）回复(0）举报 2021-08-20

我来回答

java—有没有简单的方法可以在排序数组后保留原始索引而不使用比较器？

3条答案

相关问题

热门标签

最新问答