在数组中找到一个在线性时间内比任何其他数组大两倍的数字

Question

我的任务是改进我的算法，找到一个比数组中任何其他数字大两倍的数字。它目前在 O(n^2) 中运行s，我需要在 O(n) 中使其成为运行。

func twiceAsOldExact(p []person) bool {
for i := 0; i < len(p); i++ {
    for j := 0; j < len(p); j++ {
        if j == i {
            continue
        }
        if p[i].age == 2*p[j].age {
            return true
        }
    }
}
return false
}

我考虑过使用计数排序对数组进行排序并从那里开始工作，但是我不确定这是否可行。

说我有这个数组a := []int{4,5,12,24}

算法应该 return 正确，因为 24 是 12 的两倍。

如果数组是 a := []int{4,8,10,16}

它会 return 为真，因为 8 是 4 的两倍大，或者 16 是 8 的两倍，这取决于首先完成检查的内容。

你们中的任何人对我应该如何解决这个问题有任何指示吗？部分解决方案很好，或者只是建议，因为它是为了面试，也许寻求外部帮助是不道德的（尽管那是我在工作中会做的）。

此致！

建议的解决方案

func twiceAsOldExact2(p []person) bool {
    m := make(map[int]int)
    for i := 0; i < len(p); i++ {
        m[p[i].age] = i
    }

    for i := 0; i < len(p); i++ {
        if _, ok := m[2*p[i].age]; ok {
            return true
        }
    }
    return false
}

Answer 1

将值放入地图，并针对每个值 x 检查地图中是否存在 2*x。

插入映射（实现为哈希表）和搜索平均每个操作需要 O(1)，因此映射方法接近线性 O(n)，并且比二次 O(n^2) 快得多two-loops一个（但占用内存）

Answer 2

将您的数组复制到哈希 table，然后在该哈希table 中搜索 2x。全部是 O(N)，因为有 N 个元素，而哈希 table 插入和搜索是 O(1).

在数组中找到一个在线性时间内比任何其他数组大两倍的数字

Find a number in an array that is twice as big as any other in linear time

sorting

algorithm

big-o

go