0

我正在研究一个非常简单的java类，它允许客户端创建一个整数数组并插入、删除和检查一个元素是否在这个数组中。类限制之一是数组应始终按升序排序。每次插入元素时 insert(int x) 方法调用私有排序方法是否有效还是有其他方法？

4

5 回答 5

1

如果它必须是一个数组，最好的方法是进行二进制搜索以找到插入点，将较高值的元素向上移动一位，然后将新元素放入打开的间隙中。

对于每个插入，这平均移动了一半的数组元素。

如果您可以选择使用不同的数据结构，我建议您使用 TreeMap，其中键是您要插入的整数，值是该元素被插入次数的计数。

于 2013-03-30T17:59:49.983 回答
0

Java 数组具有固定大小，如果您需要进行删除和插入，您可能需要一个列表（ArrayList 或 LinkedList）

一些替代方案：

  1. 一个列表; 对每个插入进行二进制搜索以找到插入点。

  2. 列表加地图；您保留在地图中，告诉您列表中每个整数的（第一个）索引。

  3. 一个列表; 做一个插入加一个Collections.sort(list)

1 不太直接，但最有启发性。2在速度上效率最高，但浪费空间。三是最直接、最务实。

于 2013-03-30T18:01:18.967 回答
0

数组可能不是实现您所追求的最佳方式，但这取决于您想要从您的课程中获得什么，以及哪些方法很重要，并且速度很快。

为了实现您对数组的要求，您将能够获得的最佳结果是（假设数组是无限大小/您只存储最大数量的整数）：

  • 插入：最坏情况：O(n)，平均情况：O(n)
  • 移除：最坏情况：O(n)，平均情况：O(n)
  • 按索引获取元素：始终：O(1)
  • 检查元素是否存在：最坏情况：O(log n) [二进制搜索]

如果这是您所追求的那种效率和行为，那么这就是您问题的答案：

所以你问这是否有效：

  • 将新整数添加到数组末尾：效率：O(1)
  • 对整个数组进行排序：效率：O(n * log(n))

总效率： O(n * log(n))

有一种更有效的方法，这将涉及执行以下操作：

  • 执行二分查找以查找数组中需要插入新整数的点。O(logn)
  • 将所有内容沿 1 移动到该点的右侧（以在正确的位置腾出空间）。上）
  • 插入新整数：O(1)

总效率： O(n)

不同的数据结构：

如果这不是您所追求的那种行为，那么您可能会研究一些不同类型的数据结构。例如，基于树的东西，如TreeSet将提供非常不同的效率：

  • 插入：O(log n)
  • 移除：O(log n)
  • 按索引获取元素：（我相信不可能？不熟悉此类的完整实现）
  • 检查元素是否存在：O( log n )
于 2013-03-30T19:23:02.710 回答
0

每次插入元素时如何对数组进行排序

这样做

 Arrays.sort(array);

将指定的整数数组按数字升序排序。排序算法是一种调整过的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11) P. 1249-1265（1993 年 11 月）。该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降低到二次性能。

在此处阅读 java 文档。

并在运行时增长项目而不是使用 ArrayList。

在 arrayList 中这样做。

List<String> unsortList = new ArrayList<String>();
unsortList.add("111");
unsortList.add("333");
unsortList.add("222");

//before sort
System.out.println("ArrayList is unsort");
for(String temp: unsortList){
    System.out.println(temp);
}

//sort the list
Collections.sort(unsortList);

//after sorted
System.out.println("ArrayList is sorted");
for(String temp: unsortList){
    System.out.println(temp);
}
于 2013-03-30T17:54:06.887 回答
0

我建议您使用像SortedSet< Integer >（实现类TreeSet）这样的排序集合。

始终排序并删除重复项。

如果您绝对想要一个int[]，java.util.Arrays实用程序包含搜索和排序。

于 2013-03-30T17:58:31.807 回答