英文:
Keep ArrayList sorted after every add call by finding index to add Integer very quickly (1 million add calls needed)
问题
老师要求我逐个将一个整数项添加到MySortedArray类内部的泛型ArrayList中。我必须添加1,000,000个项目。他希望我在MySortedArray中实现的自定义add方法在每次添加后都能对ArrayList进行排序。然而，在每次add()调用后进行一百万次排序太慢了。我应该怎么做？我需要能够快速找到应该在ArrayList中添加整数项的索引。二分搜索是否可行？
@Test
void testRandomInts() {
MySortedArray<Integer> ints = new MySortedArray<>(10);
for (int i = 0; i < 200; i++) {
int num = (int)(Math.random() * 10 + 1);
ints.add(num);
}
System.out.println("array is: " + ints.contents.toString());
assertTrue(isSorted(ints));
}
英文:
My teacher wants me to add an Integer item one at a time to a generic arraylist inside MySortedArray Class. I have to add 1_000_000 items. The custom add method he wants me to implement in MySortedArray, needs to add able to sort the arraylist after every addition. However, sorting it a million times after every add() call is too slow. What am I supposed to do? I need to be able to find the index in the ArrayList where I should add the Integer item very quickly. Would binary search work?
@Test
void testRandomInts() {
MySortedArray<Integer> ints = new MySortedArray<>(10);
for (int i = 0; i < 200; i++) {
int num = (int)(Math.random() * 10 + 1);
ints.add(num);
}
System.out.println("array is: " + ints.contents.toString());
assertTrue(isSorted(ints));
}
答案1
得分: 0
int index = Collections.binarySearch(contents, item);
if (index < 0) index = ~index;
contents.add(index, item);
英文:
int index = Collections.binarySearch(contents, item);
if (index < 0) index = ~index;
contents.add(index, item);
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论