插入元素與升序和重複元素

Question

我有一個家庭作業，我需要插入或添加新elemment到ArrayList<Interger>與以下條件，ArrayList的：

1. 元素必須升序。

2. 在ArrayList<Integer>

3. 插入方法運行無重複元件爲O（n）次。

這是我添加新元素前檢查重複元素的插入方法。

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<Integer> { 


    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

Answer 1

這裏是我會怎麼做：（註釋中說明）

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); 
} 

，您張貼目前的解決方案看起來大多正確的，除了它不會以升序保存元素。

Answer 2

我使用TreeSet，當我想添加非重複的元素到一個集合。試一試！

Answer 3

由於這是作業，我假設您必須使用ArrayList並手動執行邏輯（而不是使用TreeSet作爲明顯的解決方案）。我認爲下面的提示應該足以讓你完成實現:-)

如果數組元素已經按升序排列，則不需要遍歷整個數組。只需搜索等於或大於新元素的第一個元素。如果平等，你有一個愚蠢的。如果更大，請在它之前插入新元素，然後完成。如果所有現有元素都小於新元素，請將其插入最後。

這會給你所需的O（n）性能。但是，作爲改進，您可以考慮使用binary search而不是linear。

Answer 4

你爲什麼不使用TreeSet的： http://download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html

因爲這是家庭作業問題和ArrayList需要使用我改變我的答案。

您將需要線性遍歷和比較元素。採取相應的行動：

• 如果新元素等於當前元素什麼也不做並返回。
• 如果新元素大於當前元素遍歷到下一個。
• 如果新元素小於此索引處的當前元素添加元素並返回。
• 如果在遍歷時到達列表的末尾，則添加新元素並返回。 （這將在列表的末尾添加元素）

我在這裏假設所有元素都是使用上述算法添加的。所以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); 
} 

希望這有助於。

Answer 5

列表是一個列表而不是一個集合，如果它的行爲像一個集合，它會打破它的契約。在一個TreeSet插入應該是O（日誌（n））的左右......

Answer 6

爲新的數據結構創建一個類。

每當添加數據值時，對數組列表執行二進制搜索以確保數據值不存在。如果它已經存在，則引發異常。如果它不存在，則將其插入其排序位置。

在你的家庭作業中記下一個現有的數據結構（TreeSet）來執行此功能，但是通過比剛創建的更好的實現來實現此功能。

Answer 7

這是O（n）中的插入方法。

public void insert(int x) { 
    int pos = Collections.binarySearch(this, x); 
    if (pos < 0) { 
     add(-pos-1, x); 
    } 
}