主页 / 问题 / 1591838
Accepted
mygedz
Asked:2024-08-25 17:35:30 +0000 UTC2024-08-25 17:35:30 +0000 UTC

寻找唯一的号码

  • 772

我正在解决一个问题。 在此输入图像描述


import "fmt"

func main() {
    var sizeArr int
    fmt.Scan(&sizeArr)

    arr := make([]int, sizeArr)
    for i := 0; i < sizeArr; i++ {
        fmt.Scan(&arr[i])
    }

    fmt.Println(countUnique(arr))
}

func countUnique(arr []int) int {
    count := 0
    sizeArr := len(arr)

    for i := 0; i < sizeArr; i++ {
        temp := true
        for j := 0; j < sizeArr; j++ {
            if i != j && arr[i] == arr[j] {
                temp = false
                break
            }
        }

        if temp {
            count++
        }
    }
    return count
}

写了测试：

        {[]int{1, 1, 1, 1, 1}, 0},
        {[]int{1, 2, 2, 3, 4, 4, 5}, 3},
        {[]int{1, 2, 3, 4, 4, 5, 5, 6}, 4},
        {[]int{}, 0},
        {[]int{100, -100, 100, 200, -200}, 3},
        {[]int{1, 1, 2, 3, 4, 5, 5}, 3},
        {[]int{-1, -2, -2, 1, 2, 2}, 2},
        {[]int{0, 1, 1, 1, 1}, 1},
        {[]int{-2, -100, -2, -100, 0}, 1},
        {[]int{-100, -100, -2, -100, 0}, 2},
        {[]int{-100, -100, 2, -100, 0}, 2},
        {[]int{1, 1, 1, 2, 2, 2, 3, 3, 3, 5}, 1},
        {[]int{0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 1},
        {[]int{0, 0, 1, 1, 0}, 0},

但在平台上，在一些封闭测试中，它崩溃了：超出时间限制 - 2 s - 4.64 MB 告诉我该往哪个方向看......我已经伤透了脑筋。

golang

4 个回答

  1. Best Answer

    谢谢大家的建议。这个决定已经通过了。带注释的代码。

    package main

import "fmt"

func main() {
    var sizeArr int
    fmt.Scan(&sizeArr)

    // Создаем мапу
    arrMap := mapCreate(sizeArr)

    // Подсчитываем уникальные числа и выводим результат
    fmt.Println(countUnique(arrMap))
}

// Функция для создания мапы
func mapCreate(sizeArr int) map[int]int {
    var num int
    arrMap := make(map[int]int)

    for i := 0; i < sizeArr; i++ {
        fmt.Scan(&num)
        // Считаем количество вхождений каждого числа
        arrMap[num]++
    }
    return arrMap
}

// Функция для подсчета уникальных чисел
func countUnique(arrMap map[int]int) int {
    tempUnique := 0
    for _, count := range arrMap {
        if count == 1 { // встречается ли число только 1 раз
            tempUnique++
        }
    }
    return tempUnique
}
    • 3

  2. 您有一个复杂度为 O(n^2) 的算法。您可以尝试使用复杂度为 O(n*logn) 的算法对数组进行排序： https://proglib.io/p/7-sposobov-sortirovki-massivov-na-primere-ss-illyustraciyami-2022-04-20

    或使用现成的内置解决方案，例如：https://code-basics.com/ru/languages/go/lessons/slice-sort

    然后线性识别唯一值，因为您将保证知道相同的元素将彼此跟随

    • 1

  3. 你可以这样做：

    package main

import (
    "fmt"
    "strconv"
    "strings"
)

func main() {
    // Читаем количество вводимых чисел
    var sizeArr int
    fmt.Scan(&sizeArr)

    // Читаем строку с числами, разделенных пробелом
    var numbers string
    fmt.Scan(&numbers)
    
    // Разделяем по пробелу
    numbersArrStr := strings.Split(" ", numbers)
    var numbersArr = make([]int, len(numbersArrStr))

    // Конвертируем в числа
    for _, numberArrStr := range numbersArrStr {
        num, _ := strconv.Atoi(numberArrStr)
        numbersArr = append(numbersArr, num)
    }

    // Заполняем мапу
    var numbersMap = make(map[int]uint, len(numbersArr))
    for _, num := range numbersArr {
        _, exists := numbersMap[num]
        if exists {
            numbersMap[num]++
        } else {
            numbersMap[num] = 1
        }
    }

    // Считаем число уникальных
    var uniqueNumbers = 0
    for index, _ := range numbersMap {
        if numbersMap[index] == 1 {
            uniqueNumbers++
        }
    }
    fmt.Printf("Всего чисел: %d, уникальных: %d", len(numbersArrStr), uniqueNumbers)
}
    • 1

  4. 我会这样写：

    package main

import "fmt"

func main() {
    var sizeArr int
    fmt.Scan(&sizeArr)

    max := 0

    arr := make([]int, sizeArr)
    for i := 0; i < sizeArr; i++ {
        fmt.Scan(&arr[i])
        if arr[i] > max {
            max = arr[i]
        }
    }

    fmt.Println(countUnique(arr, max))
}

func countUnique(arr []int, max int) int {
    var count = 0
    var numbersCount = make([]int, max)

    for _, elem := range arr {
        numbersCount[elem-1] += 1
    }
    for _, elem := range numbersCount {
        if elem == 1 {
            count += 1
        }
    }

    return count
}

    输入：

    1 2 3 1 1 3

    结论：

    1

    该算法的复杂度为O(2n)。

    • 0

相关问题