java - 如何在Java中将一个整数插入到已排序的List中？

Question

我想编写一个函数 insertAndSort() ，它将接受整数“num”和整数列表“list”作为参数。让我们假设列表欲望已经排序。

算法应该这样工作:

1. 将“num”添加到 L 中，并在添加“num”后保持列表排序。
2. 返回排序后的列表。

警告:我们不知道列表是按 ASC 还是 DESC 排序。这正是我的问题!

示例:

• 如果 "num"= 4 并且 L = {1, 3, 5, 7}，则最终排序后的 List 为 {1, 3, 4, 5, 7}
• 如果 "num"= 4 且 L = {7, 5, 3, 1}，则最终排序后的 List 为 {7, 5, 4, 3, 1}
• 我无法使用 Collections.sort 或 Collections.reverseOrder 等排序 API...

到目前为止，我已经生成了这段代码:

public static void main(String[] args) {

    int num = 4;
    List<Integer> myList = Arrays.asList(1, 3, 5, 7);
    List<Integer> newList = new ArrayList<Integer>();
    newList = insertAndSort(myList, num);
    System.out.println(newList);

}

public static List<Integer> insertAndSort(List<Integer> list, int num) {
        List<Integer> listSecond = new ArrayList<Integer>(list.size()+1);
        for(int i = 0; i <= list.size() ; i++) {
            if(num < list.get(i)) {
                if(!listSecond.contains(num)){
                    listSecond.add(num);
                } else {
                    listSecond.add(list.get(i-1));
                    listSecond.add(list.get(i));
                    break;
                }            
            } else {
                listSecond.add(list.get(i));
            }
        }
        return listSecond;
    } 

问题在于，这似乎适用于单一类型的列表:升序列表。当我采用降序排序列表时，它不再起作用。

你有什么想法让这两种类型的列表都可以工作吗？

感谢和问候。

Answer 1

首先，您需要检测现有列表中的排序顺序。

1. 如果列表为空，您无需关心，只需添加元素即可，不能破坏任何现有的排序顺序。
2. 如果列表包含一个元素，我无法告诉您该怎么做。选项包括抛硬币和抛出异常，但还有更多。
3. 如果列表包含两个或多个元素，则迭代除最后一个元素之外的所有元素，每次将当前元素与下一个较高索引中的元素进行比较。一旦遇到一对不相等的元素，您就知道排序顺序。如果你只遇到相等的元素，那么列表中的所有元素都是相等的，我也无法告诉你该怎么做。

一旦检测到排序顺序，我建议使用一个大的 if-else 语句来分别处理这两种情况。

您已经有了升序大小写的代码。但它并不总是有效。如果我尝试将 4 插入 { 1, 3, 5 }，我会得到 ArrayIndexOutOfBoundsException 。如果我尝试使用 { 1, 3, 5, 7, 9 }，则 9 会丢失。您可能应该找到解决方案。

您应该能够像处理升序大小写一样处理降序大小写。仅使用 num > list.get(i)而不是num < list.get(i) .