使用升序将元素插入ArrayList并且没有重复元素
我有一个家庭作业，我需要插入或添加新的元素到ArrayList与以下条件：
-
元素必须按升序排列 。
-
ArrayList没有重复的元素 -
插入方法在O（n）次运行。
这是我在添加新元素之前检查重复元素的insert方法。
public void insert(int x){ //effect: Check duplicate elements if not x to the elements; boolean found = false; if(super.size()!=0){ for(int i=0; i<super.size(); i++){ if(super.get(i)==x){ found = true; } } } if(found){ return; } else{ super.add(x); } }
我该怎么做？ 谢谢。
加成
这是我的类名InSetExtra
public class IntSetExtra extends ArrayList { private static final long serialVersionUID = 1L; public IntSetExtra(){ super(); } public void insert(int x){ //effect: Check duplicate elements if not x to the elements; boolean found = false; if(super.size()!=0){ for(int i=0; i<super.size(); i++){ if(super.get(i)==x){ found = true; } } } if(found){ return; } else{ super.add(x); } } public String toString(){ //effect: return string of this. if(super.size()==0) return "[]"; String s = "[" + super.get(0).toString(); for(int i=1; i<super.size(); i++){ s += ", " + super.get(i).toString(); } return s += "]"; } }
我需要插入大尺寸的元素，例如：
IntSetExtra a, b; a = new IntSetExtra(); b = new IntSetExtra(); for(int i=0; i<30000; i++){ a.insert(2*i); } for(int i=0; i<30000; i++){ a.insert(i); } System.out.println("a sub = "+a.toString().substring(0, 37));
我该怎么办？
PS。 我的教师只需要使用ArrayList
我将如何做到这一点:(评论中的解释）
public void insert(int x){ // loop through all elements for (int i = 0; i < size(); i++) { // if the element you are looking at is smaller than x, // go to the next element if (get(i) < x) continue; // if the element equals x, return, because we don't add duplicates if (get(i) == x) return; // otherwise, we have found the location to add x add(i, x); return; } // we looked through all of the elements, and they were all // smaller than x, so we add ax to the end of the list add(x); }
您发布的当前解决方案看起来大致正确，除了它不会按升序保存元素。
这是O（n）中的插入方法。
public void insert(int x) { int pos = Collections.binarySearch(this, x); if (pos < 0) { add(-pos-1, x); } }
由于这是家庭作业，我假设您必须使用ArrayList并手动实现逻辑（而不是使用TreeSet作为明显的解决方案）。 我认为以下提示应该足以让您最终确定实施:-)
如果数组元素已按升序排列，则无需遍历整个数组。 只需搜索等于或大于新元素的第一个元素。 如果相等，你就有一个骗局。 如果更大，请在它之前插入新元素并完成。 如果所有现有元素都小于新元素，请将其插入末尾。
这将根据需要为您提供O（n）性能。 但是，作为改进，您可以考虑使用二分搜索而不是线性 搜索 。
为新数据结构创建一个类。
每当添加数据值时，对arraylist执行二进制搜索以确保数据值尚未存在。 如果它已经存在，则引发exception。 如果不存在，请将其插入其分拣位置。
在您的作业中记下存在执行此function的现有数据结构（TreeSet），但通过比您刚刚创建的实现更好的实现来实现。
为什么不使用TreeSet： http ： //download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html
由于这是HomeWork问题，需要使用ArrayList，我正在改变我的答案。
您将需要线性使用遍历并比较元素。 采取相应行动：
- 如果new元素等于当前元素什么都不做并返回。
- 如果new元素大于当前元素遍历next。
- 如果new元素小于当前元素，则在此索引处添加元素并返回。
- 如果在遍历时到达列表的末尾，则添加新元素并返回。 （这将在列表末尾添加元素）
我假设所有元素都是使用上面的算法添加的。 所以ArrayList总是排序:)。
这是代码：
public void insert(int x) { for (int i = 0; i < size(); i++) { if (x == get(i)) { // if new element is equal to current element do nothing and // return return; } else if (x > get(i)) { // if new element is greater than current element traverse to // next. continue; } // code reaches here if new element is smaller than current element // add element at this index and return. add(i, x); return; } // if end of list is reached while traversing then add new element and // return. (This will add element at the end of list) add(x); }
希望这可以帮助。
当我想将非重复元素添加到Set时，我使用TreeSet。 试一试！
列表是一个列表而不是一个集合，如果它表现得像一个集合，它就会违反合同。 在TreeSet中插入应该是O（log（n））左右……