java对整数数组进行排序，而不影响由表示的特殊字符的索引$

Question

我在面试中被问到的问题如下。 例如：包含特殊字符的整数输入数组在输入数组的几个索引处存在任何特殊字符，如#，@$：

[12,5,65,#,@,20,10,#,@,47,50,$,11,$,90,$]. Here, we have special character denoted as $ exists at index 5, 8 & 10.

排序后，特殊字符位置（索引）不应更改。这意味着输出数组应该如下所示：

[5,10,11，#，@，12,20，#，@，47,50，$，65，$，90，$]

我的答案是：根据$将数组拆分为子数组。之后，对所有子阵列分别排序，然后合并它们。但是，面试官们对此印象不深。请建议不同的方法

Answer 1

还有另一个解决方案：

• 保留一组包含$字符的所有可能索引
• 存储一个只包含数字的单独列表，以便我们以后可以对其进行排序
• 所有数字相加后，将它们分别排序
• 循环原始列表索引，如果索引集中存在当前索引，则向结果数组列表添加$。否则，请从已排序的数字中添加和删除第一个数字

示例代码：

import java.util.*;

public class SpecialSort {

    private static String DOLLAR_SIGN = "$";

    public static void main(String[] args) {
        List<Object> list = new ArrayList<>(
                          Arrays.asList(12, 5, 65, 20, 10, "$", 47, 50, "$", 11, "$", 90));

        Set<Integer> dollarSigns = new HashSet<>();
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            Object current = list.get(i);
            if (current.equals(DOLLAR_SIGN)) {
                dollarSigns.add(i);
            } else {
                numbers.add((Integer)current);
            }
        }

        Collections.sort(numbers);

        List<Object> sorted = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if (dollarSigns.contains(i)) {
                sorted.add(DOLLAR_SIGN);
            } else {
                sorted.add(numbers.remove(0));
            }
        }

        System.out.println(sorted);
    }
}

输出：

$ javac SpecialSort.java && java SpecialSort
[5, 10, 11, 12, 20, $, 47, 50, $, 65, $, 90]

Answer 2

下面是使用Streams的方法

1. 首先你记得美元符号在哪里
2. 然后你去掉美元符号
3. 然后对列表进行排序
4. 然后你再加上美元符号

private static List<Object> list = 
    Arrays.asList(12, 5, 65, 20, 10, "$", 47, 50, "$", 11, "$", 90);

public static void main(String[] args) {
    List<Integer> dollarIndices = 
            IntStream.range(0, list.size()).filter(i -> list.get(i).equals("$")).boxed()
            .collect(Collectors.toList());
    List<Integer> noDollars = 
            list.stream().filter(Integer.class::isInstance).map(Integer.class::cast)
            .collect(Collectors.toList());
    Collections.sort(noDollars);
    List<Object> withDollars = new ArrayList<>(noDollars);
    dollarIndices.stream().forEach(i -> withDollars.add(i, "$"));

    System.out.println(withDollars);
}

输出：

[5, 10, 11, 12, 20, $, 47, 50, $, 65, $, 90]

Answer 3

解决这个问题的简单算法

• 存储特殊字符串/字符的索引。这是$-Array1
• 获取数组和排序的所有整数元素。-阵列2
• 插入Array1的特殊字符串（这里是$）并与Array2合并。确保数组1元素的索引没有更改

Answer 4

最简单的排序算法之一是Selection Sort，它非常适合这种情况，因为它可以轻松跳过应该单独保留的元素

private static void sortIntegers(Object[] array) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] instanceof Integer) {
            int minIdx = i;
            int min = (Integer) array[i];
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] instanceof Integer && (Integer) array[j] < min) {
                    minIdx = j;
                    min = (Integer) array[j];
                }
            }
            if (minIdx != i) {
                array[minIdx] = array[i];
                array[i] = min;
            }
        }
    }
}

测试

Object[] array = {12,5,65,20,10,"$",47,50,"$",11,"$",90};
sortIntegers(array);
System.out.println(Arrays.toString(array));

输出

[5, 10, 11, 12, 20, $, 47, 50, $, 65, $, 90]

Answer 5

在迭代数组时比较条目，并设置一个if-else条件以跳过美元符号