Java中解决袜子商人问题的两种方法

1. 引言

在本教程中，我们将学习两种解决“袜子商人问题”的 Java 方案。

2. 袜子商人问题

在袜子商人问题中，一位商人有一大堆袜子待售，必须按颜色配对。我们用整数数组 socks 表示袜子的颜色。商人的目标是确定有多少双颜色匹配的袜子。

因此，我们有三个输入：

• n：袜子总数
• socks：存放 n 只袜子颜色的数组
• k：该数组中颜色的最大 ID，即 1 <= socks[i] <= k（对于 0 <= i < n）

例如，假设我们有 n = 7 只袜子，socks = [11, 22, 22, 11, 111, 33, 222]，且 k = 222：

[LOADING...]

这里，只有 5 种颜色。颜色 11 有一对，颜色 222 也有一对。剩下三只单独的袜子，每种颜色各一只。因此，我们返回 2 作为配对数。

3. 基于数组的解法

当已知 k 较小时，基于数组的解法是最佳选择。在这里，我们使用一个数组 counts 来统计每种袜子出现的次数，然后遍历该数组，将每个计数除以 2 来计算总配对数：

public int countPairsWithArray(int n, int[] socks, int k) {
    int[] counts = new int[k];
    int pairs = 0;
    for (int i = 0; i < n; i++) {
        counts[socks[i]]++;
    }
    for (int count : counts) {
        pairs += count / 2;
    }
    return pairs;
}

严格来说，我们可以省略参数列表中的 n，而在代码中使用 socks.length。我们保留 n 是为了更贴近问题描述，并使解决方案更易读。

该解法的时间复杂度和空间复杂度均为 O(n + k)。如果 k = O(n)，则复杂度简化为 O(n)。

4. 基于 HashSet 的解法

**当颜色 ID 范围无界、未知或非常大时，基于数组的解法性能会下降。**例如，当 k 非常大时，counts 数组不仅可能非常稀疏（大部分元素为 0）——如果唯一颜色数量远小于 k——还可能因过大而无法放入内存。

对于这种情况，我们使用 HashSet。这里的 HashSet 名为 unmatchedSocks，用于存储未配对的袜子。在遍历输入数组时，我们检查当前袜子颜色是否已存在于 unmatchedSocks 中：

• 如果不存在，则将其添加进去；
• 否则，成功找到一对！

每当找到一对，我们递增配对数计数器，并将该颜色从 unmatchedSocks 中移除，以便后续同色袜子能正确配对：

public int countPairsWithSet(int[] socks) {
    Set<Integer> unmatchedSocks = new HashSet<>();
    int pairs = 0;
    for (int sock : socks) {
        if (unmatchedSocks.contains(sock)) {
            pairs++;
            unmatchedSocks.remove(sock);
        } else {
            unmatchedSocks.add(sock);
        }
    }
    return pairs;
}

基于 HashSet 的解法的平均时间复杂度为 O(n)，因为我们只遍历一次集合，且平均情况下 HashSet 的 add() 和 size() 操作都是 O(1)。

**然而，HashSet 存在哈希冲突问题，因此当 k = O(n) 时，最坏情况下的时间复杂度为对数线性 O(n log n)。**如果 k = O(1)，时间复杂度则为 O(n)，与基于数组的算法相同。

空间复杂度为 O(n + k)。

5. 测试

5.1. 测试基于数组的解法

首先，测试基于数组的解法。

我们创建袜子数组，并将其与长度及最大颜色 ID 一起传入：

public void givenSockArray_whenUsingArray_thenReturnsCorrectPairCount() {
    SockMerchant merchant = new SockMerchant();
    int[] socks = {11, 22, 22, 11, 33, 3, 33, 111111, 33, 222222};
    int colorMax = 222223;
    int foundPairs = merchant.countPairsWithArray(socks.length, socks, colorMax);
    assertEquals(3, foundPairs);
}

我们预期测试成功返回 3。

5.2. 测试基于 HashSet 的解法

下面测试基于 HashSet 的解法：

public void givenSockArray_whenUsingSet_thenReturnsCorrectPairCount() {
    SockMerchant merchant = new SockMerchant();
    int[] socks = {11, 22, 22, 11, 33, 3, 33, 111111, 33, 222222};
    int foundPairs = merchant.countPairsWithSet(socks);
    assertEquals(3, actualPairs);
}

和之前一样，我们预期测试成功返回 3。

6. 结论

在本文中，我们针对袜子商人问题研究了基于两种不同 Java 数据结构的解法。

基于数组的方法在颜色域小且颜色 ID 连续时，速度快且内存效率高。但是，当颜色 ID 稀疏或 k 非常大时，它会浪费内存和计算时间。

另一方面，HashSet 方法更加通用，因为它能处理任意大的整数和稀疏数据集，而无需分配连续的大块内存。此外，我们还可以将 HashSet 的逻辑调整为对自定义对象或字符串进行分组。

与往常一样，完整的代码示例可在 GitHub 上找到。