没有重复的数组，算法

Question

我必须编写函数，返回给定的数组，排序，不重复。

我想出了这样的解决方案：

 public static String [] no_repeats(String [] a)
    {
        Arrays.sort(a);

        ArrayList<String> ret = new ArrayList<>();
        for (int i =1; i < a.length; i++)
                   if(a[i].compareTo(a[i-1]) != 0)
                       ret.add(a[i]);

        return  ret.toArray(ret.toArray(new String[0]));
    }

我想知道我的问题是否有更好(更快)的解决方案？像eg这样的收藏。这里不允许设置。

Answer 1

既然你需要排序，我想这是个很好的方法。该算法只需跟踪最后增加的值，以确保不添加重复值。

public static String[] no_repeats(String[] a) {
    
    Arrays.sort(a);
    
    ArrayList<String> ret = new ArrayList<>();
    String lastAdded = "";
    for (String str : a) {
        if (!str.equals(lastAdded)) {
            ret.add(str);
        }
        lastAdded = str;
    }
    return ret.toArray(new String[0]);
}

当然，您可以编写自己的最小哈希实现，以加快本地哈希集中的查找。在这种情况下，在跳过重复元素之后对进行排序将是一种方法，因为基于哈希的查找(与List.contains()调用不同)非常有效。然后你就会对更少的项目进行排序。

下面是如何使用您自己的set实现来加速这个过程。

如果元素已经存在，则

• set.add()返回false。因此，当返回
• 时，必须是第一次将其添加到列表中。
• 现在对较小的列表进行排序。
• 并返回数组。

F 213

public static String[] no_repeats(String[] a) {
    
    MiniHashSet<String> set = new MiniHashSet<>();
    
    ArrayList<String> ret = new ArrayList<>();
    
    for (String str : a) {
        if (set.add(str)) {
            ret.add(str);
        }
    }
    
    Collections.sort(ret);
    return ret.toArray(new String[0]);
}

这是一个简单的实现，它只有一个add和contains方法来加快查找过程。哈希表的大小相当大，以减少碰撞的可能性。

• 这个类使用对象的hashCode来获取适当的bucket来放置列表。
• 每个列表可以保存任何项哈希到该桶。-The返回的桶要么是数组中该索引的现有列表，要么是以前不存在的新列表。

@SuppressWarnings("unchecked")
class MiniHashSet<T> {
    int size = 10_000;
    
    List<T>[] data = new ArrayList[size];
    
    public boolean add(T val) {
        List<T> b = getBucket(val);
        if (!b.contains(val)) {
            b.add(val);
            return true;
        }
        return false;
    }
    
    public boolean contains(T val) {
        List<T> b = getBucket(val);
        return b.contains(val);
    }
    
    private List<T> getBucket(T val) {
        int i = val.hashCode() % size;
        List<T> b = data[i];
        if (b == null) {
            b = new ArrayList<>();
            data[i] = b;
        }
        return b;
    }
}

虽然这是相当多的额外工作，但这个解决方案比我提供的第一个解决方案要好得多，因为查找是有效的，并且在删除重复项之后，排序可能会发生。

Answer 2

通过使用流可以很好地解决这个问题：

public static String[] no_repeats(String[] a) {
    return Arrays.stream(a)
            .distinct()
            .sorted()
            .toArray(String[]::new);
}

Answer 3

对其排序，然后检查元素是否相等(如果是，则它们在一起)

    public static String[] no_repeats(String[] a)
    {
        Arrays.sort(a);
        ArrayList<String> al = new ArrayList<String>();
        al.add(a[0]);
        for(int i = 1;i<a.length;i++) {
            if(!a[i].equals(a[i - 1])) {
                al.add(a[i]);
            }
        }

        return  al.toArray(new String[0]);
    }