Golang数组问题在Hackerrank上的解法探讨

Golang数组问题在Hackerrank上的解法探讨 有人能帮我解决这个算法问题吗？

亚历克斯在一家服装店工作。有一大堆袜子需要按颜色配对以便销售。给定一个表示每只袜子颜色的整数数组，确定有多少双颜色匹配的袜子。

例如，有7只颜色为[1, 2, 1, 2, 1, 3, 2]的袜子。有一双颜色1和一双颜色2。剩下三只不成对的袜子，每种颜色各一只。配对数就是2。

函数描述

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

sockMerchant函数有以下参数：

  • n : 袜子堆中的袜子数量
  • ar : 每只袜子的颜色

输入格式

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

约束条件

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

输出格式

返回亚历克斯可以出售的匹配袜子对的总数。

样例输入

9
10 20 20 10 10 30 50 10 20

样例输出

3

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

// Complete the sockMerchant function below.
func sockMerchant(n int32, ar []int32) int32 {
    var newValue int32 
    for _, value := range ar {
        newValue = value/n
    }
 fmt.Printf("The value of n is %v",n )
  fmt.Printf("The value of ar is %v",ar )
 return newValue
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 1024 * 1024)

    nTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
    checkError(err)
    n := int32(nTemp)

    arTemp := strings.Split(readLine(reader), " ")

    var ar []int32

    for i := 0; i < int(n); i++ {
        arItemTemp, err := strconv.ParseInt(arTemp[i], 10, 64)
        checkError(err)
        arItem := int32(arItemTemp)
        ar = append(ar, arItem)
    }

    result := sockMerchant(n, ar)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

来源：Hackerrank


更多关于Golang数组问题在Hackerrank上的解法探讨的实战教程也可以访问 https://www.itying.com/category-94-b0.html

2 回复

你用来解决问题的逻辑是不正确的。首先，你需要为不同的颜色创建一个映射（或频率表）。例如，如果数组是 [10, 20, 20, 10, 10, 30, 50, 10, 20]，那么该数组对应的映射将如下所示 {10: 4, 20: 3, 30: 1, 50: 1}。

现在，遍历映射中的所有值，将这些值进行整数除法（除以2），并将结果加到最终答案中。请看下面的代码：

func sockMerchant(n int32, ar []int32) int32 {
    freq := map[int32]int32{}
    for _, value := range ar {
        if _,ok := freq[value]; ok {
            freq[value] += 1
        }else {
            freq[value] = 1
        }
    }
    fmt.Println(freq)
    var ans int32 = 0
    for _, value := range freq {
        ans += value/2
    }
    return ans
}

更多关于Golang数组问题在Hackerrank上的解法探讨的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


这是一个经典的计数问题，可以通过使用哈希表（在Go中是map）来高效解决。以下是正确的实现：

func sockMerchant(n int32, ar []int32) int32 {
    colorCount := make(map[int32]int32)
    var pairs int32 = 0
    
    // 统计每种颜色的袜子数量
    for _, color := range ar {
        colorCount[color]++
    }
    
    // 计算每种颜色的配对数
    for _, count := range colorCount {
        pairs += count / 2
    }
    
    return pairs
}

更简洁的版本，可以在一次遍历中完成：

func sockMerchant(n int32, ar []int32) int32 {
    colorCount := make(map[int32]int32)
    var pairs int32 = 0
    
    for _, color := range ar {
        colorCount[color]++
        // 当某种颜色的袜子数量达到偶数时，就形成一对
        if colorCount[color]%2 == 0 {
            pairs++
        }
    }
    
    return pairs
}

对于你提供的示例输入 [10, 20, 20, 10, 10, 30, 50, 10, 20]：

  • 颜色10：4只 → 2对
  • 颜色20：3只 → 1对
  • 颜色30：1只 → 0对
  • 颜色50：1只 → 0对 总计：3对

这个算法的时间复杂度是O(n)，空间复杂度是O(k)，其中k是不同颜色的数量。

回到顶部