我想编写一个函数insertAndSort(),它将一个整数“ num”和一个整数列表“ list”作为参数。假设List欲望已经被排序。
该算法应该以这种方式工作:
在L中添加“ num”,并在添加“ num”后保持列表排序。
返回排序后的列表。
警告:我们不知道列表是按ASC还是DESC排序的。那正是我的问题!
范例:
如果“ num” = 4且L = {1、3、5、7},则最终排序的列表为{1、3、4、5、7}
如果“ num” = 4且L = {7,5,3,1},则最终排序的列表为{7,5,4,3,1}
我不能使用排序API,例如Collections.sort或Collections.reverseOrder等。
到目前为止,我已经生成了以下代码:
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;
}
问题在于,这似乎只适用于一种类型的List:升序的List。
当我按降序排序时,列表不再起作用。
您是否有办法使这两种List都可以使用?
感谢致敬。
最佳答案
首先,您需要检测现有列表中的排序顺序。
如果列表为空,则无需担心,只需添加元素,就不能破坏任何现有的排序顺序。
如果列表包含一个元素,那么我无法告诉您该怎么做。选项包括扔硬币和抛出异常,但是还有更多。
如果列表包含两个或多个元素,则除了最后一个元素外,还要遍历它们,每次将当前元素与下一个较高索引中的元素进行比较。一旦遇到一对不相等的元素,就知道排序顺序。如果您仅遇到相等的元素,则列表中的所有元素都是相等的,而且我也无法告诉您该怎么做。
一旦检测到排序顺序,我建议使用if-else大语句来分别处理这两种情况。
您已经有升序代码。除非它并不总是有效。如果我尝试在{1,3,5}中插入4,则会得到一个ArrayIndexOutOfBoundsException
。如果我尝试使用{1,3,5,7,9},则9会丢失。您可能应该为此找到一个解决方法。
您应该能够像处理上升案例一样处理下降案例。仅使用num > list.get(i)
而不是num < list.get(i)
。