1

Let's say my array contains integers. I'd like to create lists, so that every list contains indexes where a particular value occured in the array. For instance, if the array was 5,0,3,5,2,5,3, we would have 4 lists (as there were 4 values):

value 5: 0, 3, 5

value 0: 1

value 3: 2, 6

value 2: 5

Currently I am attempting to figure out the highest value (in this case 5). Therefore, I create 5 lists and just add the index to the appropriate list (i.e. the 5th element of the array is 2, so I add index 5 to the 2nd list). The problem is that I created 5 lists, but there are actually 4 needed (we don't have 4 anywhere, so one list will be created unnecessarily).

Could anyone suggest a more efficient method?

2

One approach is to lazily map from element values to lists with a dictionary. On first appearance of element, create list. On future appearances, reuse corresponding list.

If you're fine with doing two passes over the input and don't want associative dictionaries, keep a list of your offset lists, and maintain an array mapping from element value to list index.

[(0,0), (1,1), (2,2), (3,3), (4,n/a), (5,4)]

This will incur an additional indirection on element lookup, but may be worth it if you expect sparseness in your values. At this point of complexity, just use a dict of lists already unless you've got something against dicts.

1

I think your approach is just fine.

You are concerned about getting 5 lists because biggest number is 5, so you can use a map with the value. The map's keys are the unique values of the array.

Here is a concrete code suggestion in JavaScript. You can try it easily in any browser debug console, just copy it into the console:

// 1. Create a test array
var mainList = [5,0,3,5,2,5,3];

// 2. To get a map, we need some unique() function for an array:
function unique(rawArray) {
    var arr = [];
    for(var i = 0; i < rawArray.length; i++) {
        if(arr.indexOf(rawArray[i]) < 0) {
            arr.push(rawArray[i]);
        }
    }
    return arr; 
}

// At this point, you get for mainList:
// [5, 0, 3, 5, 2, 5, 3]

// And for unique(mainList);:
// [5, 0, 3, 2]

// 3. Now we create a function to get the index lists:
function createMaps(uniqueList, mainList) {

    // Create and init maps.
    var maps = {};

    for (var u=0; u<uniqueList.length; u++) {
        // Create a map entry and init it with an array.
        maps[uniqueList[u]] = [];

        // Fill the array with indices.
        for (var i=0; i<mainList.length; i++) {
            if (mainList[i] == uniqueList[u]) {
                maps[uniqueList[u]].push(i);
            }
        }
    }

    return maps;
}

// 4. Now let's put the thing together:
var uniqueList = unique(mainList);
var maps = createMaps(uniqueList, mainList);
// (end of script) 

Maps will look like this:

Object {0: Array[1], 2: Array[1], 3: Array[2], 5: Array[3]}
0: Array[1]
    0: 1
2: Array[1]
    0: 4
3: Array[2]
    0: 2
    1: 6
5: Array[3]
    0: 0
    1: 3
    2: 5

Which is exactly what you wished. You see, your idea is fine.

Finally, you mentioned a "more efficient" way. This is not very specific. To get concrete answers, try to test your idea against scenarios:

  • What happens to all your index lists if you remove a value from your main list? --> Many lists must be updated.
  • dito : What happens to all your index lists if you add / insert / swap ... values into the main list?
  • How is the performance of building a set of lists?
  • What happens if you wish to combine values for indices (e.g. like you have combined indices in a relational SQL table)? How much resistance do you feel from your model?

and so on. Like this, you will see different aspects of "efficient".

1

This is my approach. Probably the same as the others, but in Java :) We iterate through all inputs, look up in our map if we already created a list for this input value, if not we create a new list. Then we just add the index of the value to the list.

public Map<Integer, List<Integer>> uniqueList(int...input) {
    Map<Integer, List<Integer>> resultMap = new HashMap<>();
    for(int i = 0; i<input.length; i++) {
        List<Integer> resultList = resultMap.get(input[i]);
        if(resultList == null) {
            resultList = new ArrayList<>();
            resultMap.put(input[i], resultList);
        }
        resultList.add(i);
    }
    return resultMap;
}
0

This is an excellent opportunity for a recursive data structure that uses polymorphism. I would make a sorted list of sorted lists. Double linked list implemented with a bubble sorted insert. The backplane list would needs to hold nodes that had a data entry and a list entry. The secondary lists would only need data entries in its nodes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.