我们能否以更低的复杂度解决这个关于袜子商人的问题？

Question

我已经解决了hackerrank的Sock Merchant问题，但是我想要减少代码复杂度（我不确定是否可能）。

John在一家服装店工作。他有很多袜子要按颜色配对销售。给定一个表示每只袜子颜色的整数数组，确定有多少双颜色相同的袜子。

例如，有n=7只颜色为ar=[1,2,1,2,1,3,2]的袜子。有1双颜色为1的袜子和1双颜色为2的袜子。还剩下3只单独的袜子，每种颜色各1只。一共有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
    ---------------------------------------

- MANITORATION

---

代码审查网站更适合此类问题。 - PM 77-1

我投票关闭此问题，因为它要求审查已经工作的代码，与主题无关。 - ekhumoro

使用ArrayList。您可以轻松地从列表中删除项目并消除最后一个for循环。 - DCR

Answer 1

你可以使用 HashSet 在单次遍历 (O(n)) 中解决这个问题。HashSet 具有 O(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++;
    }
}

- Mad Physicist

Answer 2

在Swift中，也可以使用字典来解决这个问题，示例如下：

func sockMerchant(n: Int, ar: [Int]) -> Int {
 
    var dictionary: [Int: Int] = [:]
    var totalNumberOfPairs: Int = 0
    
    // Store all array elements in a dictionary
    // with element as key and occurrence as value
    ar.forEach{
        dictionary[$0] = (dictionary[$0] ?? 0) + 1
    }
    
    // Iterate over the dictionary while checking for occurrence greater or equal 2.
    // If found add the integer division of the occurrence to the current total number of pairs
    dictionary.forEach { (key, value) in
        if value >= 2 {
            totalNumberOfPairs = totalNumberOfPairs + (value / 2)
        }
    }
    
    return totalNumberOfPairs
}

- DvixExtract

Answer 3

这适用于Java 8！

static int sockMerchant(int n, int[] ar) {
        Set<Integer> list = new HashSet<Integer>();
        int count = 0;
        for(int i= 0; i < n; i++){
            if(list.contains(ar[i])){
                count++;
                list.remove(ar[i]);
            }
            else{
                list.add(ar[i]);
            }
        }
        return count;
    }

- VMaz

---

这对于C#也适用。 - yongchang

Answer 4

你可以统计列表中数字出现的次数并将其除以2。

def sockMerchant(n, ar):
     unq = set(ar)
     count = 0
     for i in unq:
      count_vals = ar.count(i)
      if count_vals>1:
        count = count + int(count_vals/2)
     return count

- Prem

Answer 5

我们可以使用哈希表来解决这个问题，因为哈希表的复杂度是O(1)。
看下面的代码片段，我在Python中创建了一个字典，即哈希表，其中包含键和值。在字典中，每个值只有一个唯一的键。因此，在开始时，字典将为空。我们将循环遍历提供的列表并检查字典键中的值。如果该值不在字典键中，则表示它是唯一的，请将其添加到字典中。如果我们在字典键中找到该值，只需增加配对计数器并从哈希表即字典中删除该键值对即可。

def sockMerchant(n, ar):
    hash_map = dict()
    pairs = 0
    for x in range(len(ar)):
        if ar[x] in hash_map.keys():
            del hash_map[ar[x]]
            pairs += 1
        else:
            hash_map.setdefault(ar[x])
    return pairs

- Qazi Arsalan shah

Answer 6

这是我为初学者编写的简单c++代码，用于打印用户自定义向量中成对数字的数量：

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the sockMerchant function below.
int sockMerchant(int n, vector<int> ar) {
  int count=0;
  vector<int> x;
  for(int i=0;i<n;i++){
    if(ar[i]!=0)
    {
      for(int j=i+1;j<n;j++)
        {
          if(ar[i]==ar[j]){
            count++;
            ar[j]=0;
            break;
        }
    }}
  }
  return count;
}

int main()
{
  int a,b;
  vector<int> v;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>b;
    v.push_back(b);
    
  }
  cout<<sockMerchant(a,v);
}

- Hardik poudel

Answer 7

对于Javascript

function sockMerchant(n, ar) {
    // Create an initial variable to hold the pairs
    let pairs = 0;

    // create an object to temporarily assign pairs
    const temp = {};
    
    // loop through the provided array
    for (let n of ar) {

        // check if current value already exist in your temp object
        if (temp[n] in temp) {
            // if current value already exist in temp 
            // delete the value and increase pairs
            delete temp[n];
            pairs += 1;
        } else {
            // else add current value to the object
            temp[n] = n;
        }
    }

    // return pairs
    return pairs;
}

- Nte

Answer 8

function sockMerchant(n, ar) {
  //Need to initiate a count variable to count pairs and return the value
  let count = 0
  //sort the given array
  ar = ar.sort()
  //loop through the sorted array 
  for (let i=0; i < n-1; i++) {
    //if the current item equals to the next item 
    if(ar[i] === ar[i+1]){
      //then that's a pair, increment our count variable
      count++
      //also increment i to skip the next item
      i+=1
    }
  }
  //return the count value
  return count
}

sockMerchant(9, [10, 20, 20, 10, 10, 30, 50, 10, 20])

- gakin95

Answer 9

使用字典的Py3解决方案，该问题涉及编程，保留HTML，不进行解释。

def sockMerchant(n, ar):
    pair = 0
    d = {}
    for i in ar:
        if i in d:
            d[i] += 1
        if i not in d:
            d[i] = 1
    print(d)
    for x in d:
        u = d[x]//2
        pair += u
    return pair

- Divyansh

Answer 10

以下是我在HackerRank上针对Sock Merchant测试的JAVA解决方案：

import java.io.*;
import java.util.*;

public class sockMerchant {

public static void main(String[] args) {
    Scanner en = new Scanner(System.in);
    int n=en.nextInt();
    int[] hash = new int[300];
    for(int i=0; i<n; i++){
        hash[en.nextInt()]++;
    }
    long res=0;
    for(int f: hash){
        res+=f/2;
    }
    System.out.println(res);
 }
}

- J David González