我们能以较少的复杂性解决这个袜子商人的问题吗？

Question

我已经解决了hackerrank Sock Merchant问题，但我想降低代码的复杂性（我不确定这是否可能）。

约翰在一家服装店工作。他有一大堆袜子，必须按颜色配对出售。给定一个表示每只袜子颜色的整数数组，确定有多少双颜色匹配的袜子。

在下面的编辑器中完成sockMerchant函数。它必须返回一个整数，表示可用的匹配socks对的数量。

sockMerchant具有以下参数：

>

n:袜子堆中的数量

约束条件

>

1<=n<=100

1<=AR[i]<=100，其中0<=i

9
10 20 20 10 10 30 50 10 20

3

我的解决方案：

package com.hackerrank.test;

public class Solution {
    public static void main(String[] args) {
        //Initialize array
        int[] arr = new int[]{10, 20, 20, 10, 10, 30, 50, 10, 20};
        //Array fr will store frequencies of element


        System.out.println("---------------------------------------");
        System.out.println(" sockMerchant output " + sockMerchant(9, arr));
        System.out.println("---------------------------------------");

    }

    static int sockMerchant(int n, int[] ar) {
        int pairs = 0;
        int frequencyArray[] = new int[ar.length];
        int frequencyTemp = -1;
        for (int i = 0; i < ar.length; i++) {
            int count = 1;
            for (int j = i + 1; j < ar.length; j++) {
                if (ar[i] == ar[j]) {
                    count++;
                    frequencyArray[j] = frequencyTemp;
                }
            }
            if (frequencyArray[i] != frequencyTemp) {
                frequencyArray[i] = count;
            }
        }

        for (int i = 0; i < frequencyArray.length; i++) {
            if (frequencyArray[i] != frequencyTemp) {
                int divide = frequencyArray[i] / 2;
                pairs += divide;
            }
        }
        return pairs;
    }
}

输出为：

    ---------------------------------------
    sockMerchant frequency 3
    ---------------------------------------

Answer 1

您可以使用散列集在一次传递(O(n))中解决此问题，该散列集具有O(1)put和查找时间。每个元素已经在集合中，在这种情况下，它会被移除，并且pair计数器会增加，或者不是，在这种情况下，您会添加它：

int[] arr = new int[]{10, 20, 20, 10, 10, 30, 50, 10, 20};

HashSet<Integer> unmatched = new HashSet<>();
int pairs = 0;
for(int i = 0; i < arr.length; i++) {
    if(!unmatched.add(arr[i])) {
        unmatched.remove(arr[i]);
        pairs++;
    }
}