时间戳

首页 > 解决方案 > 我们能否以更简单的方式解决这个 Sock Merchant 问题？

java - 我们能否以更简单的方式解决这个 Sock Merchant 问题？

问题描述

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

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

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

功能说明

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

sockMerchant 具有以下参数：

  • n：堆中袜子的数量

  • ar：每只袜子的颜色

输入格式

第一行包含一个整数n ，即ar中表示的袜子数。第二行包含n 个以空格分隔的整数，用于描述堆中袜子的颜色ar[i]。

约束

  • 1 <= n <= 100

  • 1 <= ar[i] <= 100 其中 0 <= i < n

输出格式

返回 John 可以出售的匹配袜子的总数。

样本输入

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
    ---------------------------------------

标签： javaalgorithm

解决方案

您可以使用具有放置和查找时间的单程 ( O(n)) 来解决此问题。每个元素已经在集合中，在这种情况下它被删除并且对计数器增加，或者它不是，在这种情况下你添加它：HashSetO(1)

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++;
    }
}

推荐阅读