Поиск уникального числа

Question

Решаю задачу.


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 с - 4,64 МБ Подскажите, в какую строну смотреть... Уже голову сломал.

Answer 1

У Вас алгоритм сложностью O(n^2). Можно попробовать упорядочит массив, использовав алгоритм со сложностью O(n*logn): https://proglib.io/p/7-sposobov-sortirovki-massivov-na-primere-s-s-illyustraciyami-2022-04-20

или использовав готовые встренные решения по типу: https://code-basics.com/ru/languages/go/lessons/slice-sort

и далее уже линейное выявление уникальных значений, тк вы будете гарантировано знать, что одинаковые элементы будут идти друг за другом

Answer 2

Я бы написал вот так:

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

Answer 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)
}

Answer 4

Спасибо всем за советы. Прошло такое решение. Код с комментами.

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
}

БЛОГ НА HUSL

Поиск уникального числа

Ответы (4 шт):