时间戳

首页 > 解决方案 > What's the best way to count occurences of positive, negative, and 0 values in an unsorted array?

arrays - What's the best way to count occurences of positive, negative, and 0 values in an unsorted array?

问题描述

The below works but how would I optimize this? I imagine looping through the array would become expensive as it grows. I could create a map of the original array to store the number of occurrences for each value and then check those values for +/-/0 in another loop but that's even worse.

package main
import (
    "fmt"
)

func main() {
    arr := []int{2, 5, 6, 7, 8, 2, 4, 1, 1, 1, 2, -2, -2, 2, 2, 3, -1, 0, 0, 0, 0, 2, 5, 4, 9, 8, 7, 2, -3, -7}
    var p, n, z int = 0, 0, 0
    for _, v := range arr {
        if v > 0 {
            p++
        } else if v < 0 {
            n++
        } else if v == 0 {
            z++
        }
    }
    fmt.Println(p, n, z)
}

标签： arraysalgorithmperformancegooptimization

解决方案

如果你的输入结构是一个未排序的数组，那么 O(n) 是你能做的最好的，也就是说，遍历数组，比较每个元素一次。

如果可以的话，您可以使用两个数组和一个整数，一个数组用于负数，一个数组用于正数，以及一个整数来计算零的数量。然后，不再需要计数，您可以简单地获取数组的长度。

推荐阅读