I found that on execution line nonReps.remove(indexInNonreps); doesn't removing the object at the specified index.

Why does it happen?

My code:

 // given an array
Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};


Map<Character, Integer> map = new HashMap<>();
List<Character> nonReps = new ArrayList<>();

for (int i = 0; i < arr.length; i  ) {
    if (map.containsKey(arr[i])) {
        Integer indexInNonreps = map.get(arr[i]);
        Character characterInNonreps = nonReps.get(indexInNonreps);

        if (arr[i].equals(characterInNonreps))
            nonReps.remove(indexInNonreps);
        } else {
            nonReps.add(arr[i]);
            map.put(arr[i],nonReps.size()-1);
        }
    }
}

System.out.println(nonReps);

The code prints:

[a, b, c, d, e, f]

Expected:

[b, d, f]

CodePudding user response：

As OH GOD SPIDERS has pointed out in the comments there are two flavors of remove() method available in the List interface:

• remove(Object o) - inherited from the Collection interface, which expects an object to remove as parameter.

• remove(int index) - defined by the List interface, which expects the index of the element to be removed.

The compiler maps each method call to the most specific method (if there are some overloaded versions) based on the types of arguments, which in the case of nonReps.remove(indexInNonreps) happens to be remove(Object) because indexInNonreps is of type Integer.

If you unbox the indexInNonreps into primitive int you would face another issue - IndexOutOfBoundsException because right after the first removal, indices in the List would no longer match the indices in the Map.

To avoid this problem and to improve the performance (removal of an arbitrary element by index from a List is constful - in case of ArrayList all elements to right from the removed one need to be shifted, in the LinkedList you first need to find the target element by iterating over the list, it gives a time complexity of O(n), the same applies for removing a particular object from a list) we can firstly generate a Map which would indicate whether a particular character is repeated or not. And then construct a List of non-repeated characters.

That's how it might be done in O(n) time and using as fewer code as possible:

Map<Character, Boolean> isNonRepeatedByChar = new LinkedHashMap<>();

for (Character next : arr) {
//  isNonRepeatedByChar.merge(next, true, (v1, v2) -> false); // does the same as to lines below

    isNonRepeatedByChar.replace(next, true, false); // the key has been already encountered - changing value to false
    isNonRepeatedByChar.putIfAbsent(next, true);    // the key has NEVER been encountered before - adding the entry with value of true
}

List<Character> nonReps = new ArrayList<>();

for (Map.Entry<Character, Boolean> entry : isNonRepeatedByChar.entrySet()) {
    if (entry.getValue()) nonReps.add(entry.getKey());
}

System.out.println(nonReps);

Output:

[b, d, f]

Note: I've used a LinkedHashMap assuming that preserving the initial order of elements is important. If it's not the case - go with a plain HashMap.

In case if you're comfortable with streams you can obtain the result in a single statement:

List<Character> nonReps = Arrays.stream(arr)
    .collect(Collectors.toMap(
        Function.identity(),
        ch -> true,             // the key has NEVER been encountered before - adding the entry with value of true (i.e. non-repeated)
        (v1, v2) -> false,      // the key has been already encountered - changing value to false
        LinkedHashMap::new
    ))
    .entrySet().stream()
    .filter(Map.Entry::getValue)
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

CodePudding user response：

You can use Set to check if the character is unique or not, if not delete from noReps

    public static void main(String[] args) {
        Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};

        Set<Character> seen = new HashSet<>();
        List<Character> nonReps = new ArrayList<>();

        for (int i = 0; i < arr.length; i  ) {
            if(seen.contains(arr[i])){
                nonReps.remove(arr[i]);
            }else{
                nonReps.add(arr[i]);
                seen.add(arr[i]);
            }
        }
        System.out.println(nonReps);
    }

, output

[b, d, f]