将元素添加到列表中

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

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

将元素添加到列表中

回答

相关问题