在O(n)时间复杂度内找到数组中的元素，该元素是其他元素的两倍

从现在开始，我们要努力学习啦！今天我给大家带来《在O(n)时间复杂度内找到数组中的元素，该元素是其他元素的两倍》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

我的任务是改进我的算法，该算法可以找到一个比数组中任何其他数字大两倍的数字。目前它的运行时间为 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
}

解决方案

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

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

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

今天带大家了解了的相关知识，希望对你有所帮助；关于golang的技术知识我们会一点点深入介绍，欢迎大家关注编程网公众号，一起学习编程~