尝试在 Java 中的 ArrayList 实现中找到一个唯一的元素.获取唯一方法

Question

public class MyArrayList<T> implements MyList<T>{
    int num;        //number of things in the list
    T[] vals;       //to store the contents
    @SuppressWarnings("unchecked")
    public MyArrayList() {
        num = 0;
        vals = (T[]) new Object[3];
    }
public T getUnique(){
        T distinct = null;
        int count = 0;
        for (int i=0; i<vals.length; i++){
            distinct =  vals[i];
            for (int j = 0; j<vals.length; j++){
                if (vals[j] == vals[i]){
                    count++;
                }
                if (count == 1){
                    return distinct;
                }
            }
        }
        if (distinct == null){
            throw new IllegalArgumentException();
        }
        return distinct;
    }

我正在尝试一种独特的方法。一个方法 getUnique，它不带任何参数，并返回列表中仅出现一次的第一个值。(例如，调用列表 [1,2,3,1,2,4] 上的方法将返回 3，因为 1 和2 两者都出现不止一次。如果列表为空或其所有值都出现多次，该方法将抛出 NoSuchElementException

Answer 1

我已经在您的代码中添加了一些 FIXME：

public T getUnique(){
    T distinct = null;
    int count = 0; // FIXME: move this initialization inside the i loop
    for (int i=0; i<vals.length; i++){
        distinct =  vals[i];
        for (int j = 0; j<vals.length; j++){
            if (vals[j] == vals[i]){ // FIXME: use .equals() not ==
                count++;
            }
            if (count == 1){ // FIXME: move this check outside the j loop
                return distinct;
            }
        }
    }
    if (distinct == null){ //FIXME: no check needed, just throw it
        throw new IllegalArgumentException();
    }
    return distinct; //FIXME: no valid return can reach this point
}

Answer 2

Patrick Parker 的建议将修复您的代码，但我想为在列表中查找唯一元素的问题提供一个更干净、更快速的解决方案。此算法按时间O(n)运行，而不是O(n^2) 。

public static <T> Optional<T> getUnique(List<T> ls) {
    // Create a map whose keys are elements of the list and whose values are
    // lists of their occurences. E.g. [1,2,3,1,2,4] becomes {1->[1, 1],
    // 2->[2, 2], 3->[3], 4->[4]}. Then elements.get(x).size() tells us how
    // many times x occured in ls.
    Map<T, List<T>> elements = ls.stream()
            .collect(Collectors.groupingBy(x -> x));
    // Find the first element that occurs exactly one time in ls.
    return ls.stream().filter(x -> elements.get(x).size() == 1)
            .findFirst();
}

你可以这样称呼它：

Integer[] vals = {1,2,3,1,2,4};
System.out.println(getUnique(Arrays.asList(vals))
        .orElseThrow(NoSuchElementException::new));

此代码使用 Java 8 流和Optional 。下面是不使用 Java 8 语言功能的相同算法的另一个实现;如果您从未遇到过流，您可能会发现它更容易理解。

private static <T> T getUnique(List<T> arr) {
    Map<T, Integer> numOccurrences = new HashMap<>();
    for (T item : arr) {
        numOccurrences.put(item, 1 + numOccurrences.getOrDefault(item, 0));
    }
    for (T item : arr) {
        if (numOccurrences.get(item) == 1) {
            return item;
        }
    }
    throw new NoSuchElementException();
}