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

Question

我的任务是改进我的算法，找到一个比数组中任何其他数字大两倍的数字。它目前在 O(n^2) 中运行，我需要让它在 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}

算法应该返回 true，因为 24 是 12 的两倍。

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

它会返回 true，因为 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

将值放入 map ，对于每个值 x 检查 2*x 是否出现在 map 中。

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