CODEWITHSUNDEEP
javaarraysalgorithmlist
Chandra Sekhar
Chandra Sekhar

Reputation: 19492

Adding elements to a list

I have a list of some elements.

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

Assume the list contains values as below:

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

How do I add a dummy element (E.g. -1) as a separator before each of the group? he result should be

-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

How do I do that efficiently?

Upvotes: 1

Views: 155

Answers (5)

Khaled.K
Khaled.K

Reputation: 5940

Here's my solution, in case repeating integers are sorted.

Sorted repeating integers example:

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

Code

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

Upvotes: 0

Dileep
Dileep

Reputation: 5440

EDIT

Method 1:

By overriding the add() function.

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

Now list.add(number); will override the add function and adds another integer (ie-1), whenever it finds a change in value from the last element.

Method 2

In the traditional way. Iterate Over and add -1 when a change is found. 

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

Upvotes: 2

Pham Trung
Pham Trung

Reputation: 11284

If you only need to know the value and the number of element in each group, you can use two arrays. For example, if you have n different distinct values (or n group) , you can have an array int[] value and int[]count with value[i] is the value of the ith group and count[i] is the number of element in the ith group.

So in your case : 

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

To convert from the list to value and count, you just need to do two binary search for finding start and end indexes of a specific value in the list (if list is sorted). So the time complexity will be O(nlog m) with m is the size of list.

As Zoyd mentions in his comment, we also can use HashMap <Integer,Integer> to store the value and number of element pair, or TreeMap<Integer, Integer> to maintain their sorted orders.

Upvotes: 0

indivisible
indivisible

Reputation: 5012

You just need to keep track of the previous values and iterate through the list.

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

The same methodology could be followed as items are added to the original list. Either keep track of the last value added or peek at the last element.

Upvotes: 1

Bassel Kh
Bassel Kh

Reputation: 1981

Use Linked hash map, do for loop over the array, put the number as key and frequency as value. NO need to put separators at all.

Upvotes: 0

Related Questions