主页 / 问题 / 1109867
Accepted
Str
Asked:2020-04-14 00:43:41 +0000 UTC2020-04-14 00:43:41 +0000 UTC

请帮我修复并找到错误。

  • 772

大家好，大体上是这样的。我们需要编写代码，根据 Shell 算法对数组进行排序，并将单词的原始位置存储在未排序的数组中，以便可选地指示单词在排序前占据的位置。

引入一维数组并创建包含单词位置的二维数组的代码 -

 public static String [][] sortInZweid(String[] array){
        String[][] arrN = new String [array.length][2];
        int counterForIndex = 1;
        int counterForString = 0;
        for(int i = 0; i < array.length; i++){
                arrN[i][counterForString] = array[i];
                arrN[i][counterForIndex] = Integer.toString(i);
        }
        return arrN;
     }
Код, который нужно переписать чтобы метод принимал двумерный массив и сохранял после сортировки позицию слова в несортированном массиве. Например - 
                                           "Borija" , "1";
                                           "Dima" , "2";
                                           "Anna" , "3";
После сортировки должно выглядеть так -    "Anna" ,"3";
                                           "Borija" , "1";
                                           "Dima" , "2";

要重写的代码 -

int sort(String [] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i += 1) {
                final String temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap].compareTo(temp) > 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
        return 0;
    }

我重写的代码，但它不能正常工作，我已经解析了一整天，但我不明白为什么 -

int sort(String [][] arr) {
        for (int gap = arr[0].length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr[0].length; i += 1) {
                final String temp = arr[i][0];
                final String index = arr[i][1];
                int j;
                for (j = i; j >= gap && arr[j - gap][0].compareTo(temp) > 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j][0] = temp;
                arr[j][1] = index;
            }
        }
        return 0;
    }
java

3 个回答

  1. 如果您需要原始单词索引，只需在排序之前创建一个字典：

    word -> 未排序数组中的索引。

    Map<String, List<Integer>> indices = new HashMap<>();

    在这里隔离二维数组是没有意义的。排序算法本身可以保持不变。

    或者排序不是行而是对

    Pair<String, Integer> = ImmutablePair.of(arr[i], i);

    您还可以创建自己的 StringAndIndex 类，在排序算法内部进行比较时只考虑字符串本身。

    class StringAndIndex {
    int index;
    String str;
    public StringAndIndex(String str, int idx) {
         this.index = idx;
         this.str = str;
    }
}
    • 1
  2. Best Answer

    您不会阅读评论中所写的内容。

    1. 在循环中替换arr[0].length=>arr.length
    2. String[] temp = arr[i]; ... arr[j] = temp;

    到最后

    static int sort(String [][] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i += 1) {
            String[] temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap][0].compareTo(temp[0]) > 0; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
    return 0;
}

    一切正常

    [Anna, 2]
[Borija, 0]
[Dima, 1]
    • 1

  3. 至于我，创建类的想法比二维数组好。最后一个是相当的拐杖。

    import java.util.Arrays;

class ShellSort {

    int sort(Pair arr[]) {        
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i += 1) {
                final Pair temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap].compareTo(temp) > 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
        return 0;
    }

    public static void main(String args[]) {
        String arr[] = {"xxx", "aaa", "ccc", "bbb", "zzz"};
        System.out.println("Array before sorting");
        System.out.println(Arrays.toString(arr));

        ShellSort ob = new ShellSort();
        Pair[] array = Pair.of(arr);
        ob.sort(array);

        System.out.println("Array after sorting");
        System.out.println(Arrays.toString(array));
    }
}


class Pair implements Comparable<Pair>{

    private final int index;
    private final String name;

    public Pair(Integer index, String name) {
        this.index = index;
        this.name = name;
    }

    public int getIndex() {
        return index;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name + "->" + index;
    }

    @Override
    public int compareTo(Pair pair) {
        return this.name.compareTo(pair.getName());
    }

    public static Pair[] of(final String[]arr){
        final Pair[] pairs = new Pair[arr.length];
        for (int i = 0; i < arr.length; i++) pairs[i] = new Pair(i, arr[i]);
        return pairs;
    }

}
    • 1

相关问题