从数组中捕获重复项，而无需使用任何内置函数 [英] Capture duplicates from array without using any inbuilt functions

问题描述

我被赋予了编写自己的实现以从数组中删除重复对象的任务.数组未排序.

I have been given a task to write my own implementation for removing duplicate objects from an array. The array is unsorted.

作为一个例子，我有这个对象数组

As an example, I have this array of objects

ItemsList[] objects = {
                new ItemsList("ob1"),
                new ItemsList("ob2"),
                new ItemsList("ob2"),
                new ItemsList("ob1"),
                new ItemsList("ob3")
        };

"ob1" stands for itemId

我的目标是获取类似于此 ["ob1"，"ob2"，"ob3"] 的结果数组，但是在尝试查找未加倍查找的对象时给出了NullPointerException并将它们添加到数组中.

My goal is to get the result array like this ["ob1", "ob2", "ob3"], but given NullPointerException when trying to find objects that aren't doubled and add those to array.

注意:不能使用Set，HashSet，ArrayList，Arrays.copyOf，Sort等或任何其他工具(例如迭代器).

到目前为止，我已经做到了:

So far I've done this:

public String[] removeDuplicates(ItemsList[] objects) {
        String[] noDubs = new String[objects.length];
        int len = objects.length;
        int pos = 0;

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (objects[i].getItemId().equals(objects[j].getItemId())) {
                    noDubs[pos] = objects[i].getItemId();
                    pos++;
                }
                else {
                    //NullPointerException given
                    if (!objects[i].getItemId().equals(objects[j].getItemId()) && !objects[i].getItemId().contains(noDubs[i])) {
                        noDubs[pos] = objects[i].getItemId();
                        pos++;
                    }
                }
            }

        }
        String[] result = new String[pos];
        for(int k = 0; k < pos; k++) {
            result[k] = noDubs[k];
        }
        return result;
    }

getItemId 是类ItemsList方法

getItemId is class ItemsList method

推荐答案

最好使用中间的布尔数组来跟踪重复项并定义结果数组的长度.当同一元素可能出现2次以上时，这将有助于检测多个重复项.

It would be better to use an intermediate array of booleans to track the duplicates and define the length of the result array. This would facilitate detection of multiple duplicates when the same element might occur more than 2 times.

此外，我们需要确保在 ItemList 中正确覆盖方法 equals (可能还有 hashCode ):

Also, we need to make sure the method equals (and possibly hashCode) is properly overridden in ItemList:

// class ItemList
public boolean equals(Object o) {
    if (null == o || !(o instanceof ItemList)) {
        return false;
    }
    if (o == this) return true;
    ItemList that = (ItemList) o;
    return Objects.equals(this.itemId, that.itemId);
}

public int hashCode() {
    return Objects.hash(this.itemId);
}

在检查 ItemList 的相等性时，最好使用 Objects.equals 处理 null 值而不抛出 NullPointerException.因此，输入 items 中重复的 null 条目也将被过滤掉.

When checking for equality of ItemList it may be better to use Objects.equals to handle null values without throwing a NullPointerException. Thus, duplicate null entries in the input items will be filtered out too.

public static String[] removeDuplicates(ItemList[] items) {
    final int n = items.length;
    if (n < 1) {
        return new String[0];
    }
    boolean[] dups = new boolean[n];
    int dupCount = 0;

    for (int i = 0; i < n; i++) {
        ItemList current = items[i];
        for (int j = i + 1; j < n; j++) {
            if (dups[j]) {
                continue;
            }
            if (Objects.equals(current, items[j])) {
                dups[j] = true;
                dupCount++;
            }
        }
    }
    String[] output = new String[n - dupCount];
    for (int i = 0, j = 0; i < n; i++) {
        if (!dups[i]) {
            output[j++] = null == items[i] ? "<NULL>" : items[i].getItemId();
        }
    }
    // info message
    System.out.printf("Found and removed %d duplicate value%s%n", dupCount, dupCount != 1 ? "s" : "");
    return output;
}

测试:

ItemList[] items = {
    null, new ItemList("ob1"), new ItemList("ob2"), new ItemList("ob2"), new ItemList("ob1"),
    new ItemList("ob3"), null, new ItemList("ob3"), new ItemList(null), new ItemList("ob5"),
    new ItemList("ob2"), new ItemList(null), new ItemList("ob4"), new ItemList("ob5"), null,
};

System.out.println(Arrays.toString(removeDuplicates(items)));

// compare removal of duplicates to using set
System.out.println("\nUsing Set");
Set<ItemList> set = new LinkedHashSet<>(Arrays.asList(items));  
System.out.println(set);

输出:

Found and removed 8 duplicate values
[<NULL>, ob1, ob2, ob3, null, ob5, ob4]

Using Set
[null, {id=ob1}, {id=ob2}, {id=ob3}, {id=null}, {id=ob5}, {id=ob4}]

这篇关于从数组中捕获重复项，而无需使用任何内置函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！