將元素添加到列表中

我有一些元素的列表。將元素添加到列表中

List<Integer> list = new ArrayList<Integer>();

假設列表中包含值如下：

0,0,0,0,0,1,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4

如何每個組的前添加一個虛設的元素（例如-1）作爲分隔符？他的結果應該是

-1,0,0,0,0,0,-1,1,1,1,1,-1,2,2,2,2,2,-1,3,3,3,3,3,3,3,3,-1,4,4,4,4,4,4,4

我該如何有效地做到這一點？

來源

2014-04-30 Chandra Sekhar

http://docs.oracle.com/javase/7/docs/api/java/util/List.html#add%28int,%20E%29 –

這是什麼要求背後的主要想法，你會這樣做，可能會有一個替代方案和更好的解決方案 –

我不認爲你會比通過列表進行強力迭代更好，原因很簡單，你需要比較每一對連續的元素。所以你不可能比O（n）做得更好。 –

EDIT

方法1：

通過重寫add()函數。

List<Integer> list = new ArrayList<Integer>(){ 
    public boolean add(Integer add){ 
    if(super.size()==0 || super.get(super.size()-1)!=add) 
     super.add(-1); 
    super.add(add); 
    return true; 
    } 
};

現在list.add(number);將覆蓋附加功能，並增加另一個整數（即-1），每當它發現從最後元件值的變化。

方法2

在傳統的方式。迭代結束並在找到更改時添加-1。

List<Integer> list = new ArrayList<Integer>(); 
     list.addAll(Arrays.asList(0,0,0,0,0,1,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4)); 
     int last=-1; 
     for(int i=0;i<list.size();i++){ 
      if(list.get(i)!=last){ 
       last=list.get(i); 
       list.add(i, -1); 
       ++i; 
      } 
     }

來源

2014-04-30 09:15:08 Dileep

使用鏈接哈希映射，對數組進行循環，將數字作爲鍵和頻率作爲值。不需要放置分隔符。

來源

2014-04-30 08:19:29

您只需要跟蹤以前的值並遍歷列表。

List<Integer> origList = getListHowever(); 
List<Integer> spacedList = new ArrayList<Integer>(); 
int bufferElement = -1; 
int currVal; 
int lastVal = Integer.MIN_VALUE; // or some default value that is unlikely to be in the list 

for (int i=0; i<origList.size(); i++) { 
    currVal = origList.get(i); 
    if (lastVal != currVal) { 
     spacedList.add(bufferElement); 
    } 
    spacedList.add(currVal); 
    lastVal = currVal; 
}

隨着項目被添加到原始列表中，可以遵循相同的方法。要麼跟蹤最後添加的值，要麼查看最後一個元素。

來源

2014-04-30 08:20:11 indivisible

請使用'int curVal = origList.get（i）;'並且指出，您現在在每個循環中執行'origList.get（i）'3次。 –

如果您只需要知道每個組中元素的值和數量，則可以使用兩個數組。例如，如果您有n個不同的值（或n個組），則可以有一個數組int[] value和int[]count，其中value[i]是第i組的值，count[i]是第i組中的元素的數目。

所以你的情況：

int [] value = new int[5]; 
int [] count = new int[5]; 
value[0] = 0; 
count[0] = 5; 
value[1] = 1; 
count[1] = 4; 
......

要從list轉換爲value和count，你只需要在list查找特定值的起點和終點指標做兩個二進制搜索（如果list已排序）。所以時間複雜度將是O（nlog m），其中m是list的大小。

由於Zoyd在他的評論中提到的，我們還可以使用HashMap <Integer,Integer>存儲元件對的價值和數量，或TreeMap<Integer, Integer>保持自己的排序順序。

來源

2014-04-30 08:27:44

這是我的解決方案，以防重複整數排序。

排序重複整數例如：

0,0,0,1,1,1,2,2,3,3,3,3,4,4,4

代碼

class FrequencyOrderedSet 
{ 
    LinkedHashMap<Integer,Integer> list; 

    public FrequencySet() 
    { 
     list = new LinkedHashMap<Integer,Integer>(); 
    } 

    public void insert (Integer number) 
    { 
     if (list.constainsKey(number)) 
      list.put(number, list.get(number)+1); 
     else 
      list.put(number, 1); 
    } 

    public void remove (Integer number) 
    { 
     if (list.containsKey(number)) 
      if (list.get(number) > 1) 
       list.put(number, list.get(number)-1); 
      else 
       list.remove(number); 
    } 

    public ArrayList getList() 
    { 
     ArrayList out = new ArrayList<Integer>(); 

     for (Integer num : list.getKeyList()) 
      for (int i=0; i<list.get(num); i++) 
       out.add(num); 
    } 
}

來源

2014-04-30 08:52:44

將元素添加到列表中

回答

相關問題