数组中去除重复项 - Java

Question

为了进行Java练习，我正在尝试在我的EmployeesDirectory类中创建一个方法来：

• 从数组中删除重复的条目
• 删除重复条目后，数组的长度应该保持不变
• 非空条目应该构成数组的连续序列 - 而actualNum应该记录这些条目

重复指：相同的姓名、职位和工资

以下是我的当前代码：

我不确定如何实现这个方法 - 任何帮助将不胜感激

class EmployeeDirectory {

    private Employee dir[];
    private int size;
    private int actualNum;

    public EmployeeDirectory(int n) {
        this.size = n;
        dir = new Employee[size];
    }

    public boolean add(String name, String position, double salary) {
        if (dir[size-1] != null) {
            dir[actualNum] = new Employee(name, position, salary);
            actualNum++;
            return true;
        } else {
            return false;
        }
    }
}

- RandomMath

---

你的意思是只删除姓名相同的重复员工吗？ - MChaker

@MChaker，它们指的是 a.equals(b) == true 的对象。 - Alex Salauyou

Answer 1

首先，在Employee类中，覆盖equals和hashCode方法如下：

@Override
public boolean equals(Object other) {
    if(this == other) return true;

    if(other == null || (this.getClass() != other.getClass())){
       return false;
    }

    Employee guest = (Employee) other;
    return  Objects.equals(guest.name, name) 
            && Objects.equals(guest.position, position) 
            && Objects.equals(guest.salary, salary); 
}

@Override
public int hashCode() {
    return Arrays.hashCode(new Object[] {
               name, 
               position, 
               salary
        });
}

然后你可以使用Stream API的distinct方法来删除重复项

返回一个流，其中包含此流中不同的元素（根据Object.equals(Object)确定）。

你可以这样做

Employee e1 = new Employee("John", "developer", 2000);
Employee e2 = new Employee("John", "developer", 2000);
Employee e3 = new Employee("Fres", "designer", 1500);

Employee[] allEmployees = new Employee[100];
allEmployees[0] = e1;
allEmployees[1] = e2;
allEmployees[2] = e3;

allEmployees = Arrays.asList(allEmployees).stream().distinct()
            .toArray(Employee[]::new);

Arrays.asList(allEmployees).forEach(System.out::println);

输出：（保留空和非空条目）

John developer 2000.0
Fres designer 1500.0
null

- MChaker

---

我认为它相当不错（我也喜欢Java 8的特性），但是你的equals()方法容易出错，除非保证name和position不为空。 - Alex Salauyou

你的 hashCode() 很差，通常应该由对象所有非静态属性组合而成。 - Alex Salauyou

@SashaSalauyou 现在怎么样了？ - MChaker

如果 this.name 为空，你会得到 NPE——这就是我的意思。 - Alex Salauyou

嗯，我看到你正在尝试，但是如果 this.name == null 和 other.name == null 呢？在实践中，如果其他属性相等，这些对象应该是相等的。但是你的代码会返回 false。 - Alex Salauyou

Answer 2

我更希望你不要写一个专门的方法来去除重复项。如果我是你，我会在add方法中搜索重复项，然后立即决定是否需要添加Employee。

此外，为什么不使用Sets（HashSet 的链接）而不是数组来完成你的目的？根据其定义，集合不允许添加重复项，因此它们似乎是解决方案的合适选择。

- Lysenko Andrii

---

@SashaSalauyou，如果您需要与插入它们的顺序相同的元素顺序，则可以使用LinkedHashSet来实现 :) - Lysenko Andrii

使用 LinkedHashSet 会失去以 O(1) 的时间复杂度查询项目索引的能力。 - Alex Salauyou

我建议在初始数组上进行操作，当发现重复项时向左移动项目，就像我在我的答案中所示。 - Alex Salauyou

TreeSet 怎么样？ - remipod

@remipod，按值访问TreeSet的时间复杂度为O(log n)，比HashSet慢。 - Alex Salauyou

Answer 3

很遗憾，我没有得到Employee类来验证我的代码，但是请尝试以下内容：

void removeDuplicates() {
    int length = dir.length;
    HashSet set = new HashSet(Arrays.asList(dir));
    dir = new Employee[length];
    Employee[] temp = (Employee[]) set.toArray();
    for (int index = 0; index < temp.length; index++)
        dir[index] = temp[index];
}

代码在删除重复项后，必须保持数组的大小不变。数组的开头必须是有效的员工，结尾必须是空值。 不要忘记将以下内容添加到您的.java文件开头。

 import java.util.Arrays;
 import java.util.HashSet;

- Lysenko Andrii

Answer 4

如果您的任务要求为“从array中删除重复项”（即不能使用ArrayList或控制添加项时），您可以采用以下方法：

public void removeDuplicates() {
    Set<Employee> d = new HashSet<>();  // here to store distinct items
    int shift = 0;
    for (int i = 0; i > dir.length; i++) {
        if (d.contains(dir[i])) {       // duplicate, shift += 1
            shift++;
        } else {                        // distinct
            d.add(dir[i]);              // copy to `d` set
            dir[i - shift] = dir[i];    // move item left
        }
    } 
    for (int i = d.size(); i < dir.length; i++)
        dir[i] = null;                  // fill rest of array with nulls

    actualNum = d.size();
}

这里，shift变量存储目前为止在数组中找到的重复项数量。每个不同的项目都向左移动shift个位置，以使序列连续而保持初始顺序。然后剩余的项目被改为null。

为了使基于哈希的集合与Employee实例正确地工作，您还需要按照以下方式覆盖hashCode()和equals()方法：

public class Employee {

    //...

    @Override
    public int hashCode() {
        return Objects.hash(name, position, salary);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (!o.getType().equals(this.getType()) return false;
        Employee e = (Employee) o;
        return Objects.equals(e.name, name) 
            && Objects.equals(e.position, position) 
            && Objects.equals(e.salary, salary); // or e.salary == salary, if it primitive type
    }
}

- Alex Salauyou

---

将单个字符作为引用名称是不好的实践。引用名称应具有意义。此外，您可能没有理解集合的含义。集合不能包含相等的对象。 - Lysenko Andrii

“你可能还没有理解什么是集合”——抱歉，我不能以这种突然的方式继续讨论。 - Alex Salauyou

我并不是有意冒犯你，但是Set本身会“跳过”它已经包含的所有对象。此时你的代码没有意义。请阅读文档。抱歉。 - Lysenko Andrii

使用Hashset存储不同的项是一个好方法，加1。但是OP的问题说“重复”意味着相同的姓名、职位和薪水，而不是相同的对象引用？ - MChaker

@MChaker 刚刚添加了 hashCode() 和 equals() 的重写。 - Alex Salauyou