Is there any **effective way **of comparing elements in Java and print out the position of the element which occurs once. For example: if I have a list: ["Hi", "Hi", "No"], I want to print out 2 because "No" is in position 2. I have solved this using the following algorithm and it works, BUT the problem is that if I have a large list it takes too much time to compare the entire list to print out the first position of the unique word.

ArrayList<String> strings = new ArrayList<>();

for (int i = 0; i < strings.size(); i  ) {
    int oc = Collections.frequency(strings, strings.get(i));
    if (oc == 1)
        System.out.print(i);
        break;
}

CodePudding user response：

I can think of counting each element's occurrence no and filter out the first element though not sure how large your list is.

Using Stream:

List<String> list = Arrays.asList("Hi", "Hi", "No");
//iterating thorugh the list and storing each element and their no of occurance in Map
Map<String, Long> counts = list.stream().collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()));
String value = counts.entrySet().stream()
                    .filter(e -> e.getValue() == 1) //filtering out all the elements which have more than 1 occurance
                    .map(Map.Entry::getKey) // creating a stream of element from map as all of these have only single occurance
                    .findFirst() //finding the first element from the element stream
                    .get();
System.out.println(list.indexOf(value));

EDIT:
A simplified version can be

Map<String, Long> counts2 = new LinkedHashMap<String, Long>();
for(String val : list){
    long count = counts2.getOrDefault(val, 0L);
    counts2.put(val,   count);
}
for(String key: counts2.keySet()){
    if(counts2.get(key)==1){
        System.out.println(list.indexOf(key));
        break;
    }
}

The basic idea is to count each element's occurrence and store them in a Map.Once you have count of all elements occurrences. then you can simply check for the first element which one has 1 as count.

CodePudding user response：

You can use HashMap.For example you can put word as key and index as value.Once you find the same word you can delete the key and last the map contain the result.

CodePudding user response：

If there's only one word that's present only once, you can probably use a HashMap or HashSet Deque (set for values, Deque for indices) to do this in linear time. A sort can give you the same in n log(n), so slower than linear but a lot faster than your solution. By sorting, it's easy to find in linear time (after the sort) which element is present only once because all duplicates will be next to each other in the array.

For example for a linear solution in pseudo-code (pseudo-Kotlin!):

counters = HashMap()
for (i, word in words.withIndex()) {
   counters.merge(word, Counter(i, 1), (oldVal, newVal) -> Counter(oldVald.firstIndex, oldVald.count   newVal.count)); 
   
}

for (counter in counters.entrySet()) {
    if (counter.count == 1) return counter.firstIndex;
}

class Counter(firstIndex, count)

CodePudding user response：

Map<String,Boolean> loops

Instead of using Map<String,Integer> as suggested in other answers.

You can maintain a HashMap (if you need to maintain the order, use LinkedHashMap instead) of type Map<String,Boolean> where a value would denote whether an element is unique or not.

The simplest way to generate the map is method put() in conjunction with containsKey() check.

But there are also more concise options like replace() putIfAbsent(). putIfAbsent() would create a new entry only if key is not present in the map, therefore we can associate such string with a value of true (considered to be unique). On the other hand replace() would update only existing entry (otherwise map would not be effected), and if entry exist, the key is proved to be a duplicate, and it has to be associated with a value of false (non-unique).

And since Java 8 we also have method merge(), which expects tree arguments: a key, a value, and a function which is used when the given key already exists to resolve the old value and the new one.

The last step is to generate list of unique strings by iterating over the entry set of the newly created map. We need every key having a value of true (is unique) associated with it.

List<String> strings = // initializing the list
        
Map<String, Boolean> isUnique = new HashMap<>(); // or LinkedHashMap if you need preserve initial order of strings
        
for (String next: strings) {
    isUnique.replace(next, false);
    isUnique.putIfAbsent(next, true);
//      isUnique.merge(next, true, (oldV, newV) -> false); // does the same as the commented out lines above
    }
        
List<String> unique = new ArrayList<>();
        
for (Map.Entry<String, Boolean> entry: isUnique.entrySet()) {
    if (entry.getValue()) unique.add(entry.getKey());
}

Stream-based solution

With streams, it can be done using collector toMap(). The overall logic remains the same.

List<String> unique = strings.stream()
    .collect(Collectors.toMap( // creating intermediate map Map<String, Boolean>
        Function.identity(),   // key
        key -> true,           // value
        (oldV, newV) -> false, // resolving duplicates
        LinkedHashMap::new     // Map implementation, if order is not important - discard this argument
    ))
    .entrySet().stream()
    .filter(Map.Entry::getValue)
    .map(Map.Entry::getKey)
    .toList(); // for Java 16  or collect(Collectors.toList()) for earlier versions