袜子商人的问题：我正在尝试用一种不同的方法来做这件事

Question

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

例如，有n=7颜色ar=[1,2,1,2,1,3,2]的袜子。有一对颜色1和一对颜色2。剩下三只零零散散的袜子，每种颜色一只。对数为2。

我的代码：

class Sock
{
    public static void  main(String args[])
    {
        int n=10;
        int ar[] = new int[]{1,1,3,1,2,1,3,3,3,3};
        int count = 0,number=0;

        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(ar[i]==ar[j])
                {
                    count++;
                }
            }

             if(count%2==0)
                number++;

        }
        System.out.println("Pairs =  "+number);
    }
}

我试着用不同的方法来做这个问题。例如：首先ar[0]=1频率是3，count=3包含自身，然后如果count>1和如果count%2==0则增加number++，所以如果1来ar[2]=1然后再次从ar[2]=1计数1的频率。然后我们得到了1的频率3,2,1从AR[0]到AR[6],AR[2]到AR[6],AR[4]到AR[6]。

因此我们得到1's对1time,'2's对1time:total=2pair。

Answer 1

如果使用哈希表，这可以在O(n)时间复杂度和O(n)空间中完成。

Hashtable将具有Key=Socks的颜色，Value=每种颜色的总数。

total_count = dict()
for i in range(len(arr)):
    if arr[i] in total_count:
        total_count[arr[i]] += 1

pairs = 0
for i in total_count:
    pairs += int(total_count[i] / 2)

print(pairs)

在数组上迭代一次，并将每次出现的颜色存储在哈希表中。然后对哈希表进行迭代，检查每种颜色的计数是否可以被2整除。那就给你双鞋了。