如何在不使用运算符和映射或使用 o(n) 且少于 15 行代码的情况下查找数组元素是其他元素的两倍

Question

我有一个关于编码的问题。我想就下面的问题从你那里得到一些指示。有一个整数数组。这些数组数字表示人的年龄。如果列表中有一个人的年龄正好是其他人的两倍，则编写一个函数返回 true，否则该函数返回 false。

以下是约束。

• Age 是一个整数，取值范围为 0 到 50

• 您只能使用数字类型的变量（没有数组/切片/映射）

• 必须具有线性时间复杂度，只有一个循环

• 您不得使用加法、减法、乘法、除法或模运算符

• 该函数不能包含超过 15 行代码

• 该函数不能调用其他函数

假设列表已排序，我可以提出以下功能

// Go 函数：假设，年龄列表已排序。

func isPersonTwiceOldAsOthers(person []Person) bool {

    if len(person) < 2 {

        fmt.Printf("Need minimum 2 person's age to continue\n")

        return false

    }

    seen := make(map[int]bool, 15)

    for index, _ := range person {

        if seen[person[index].Age] {

            return true

        }

        seen[person[index].Age*2] = true

    }

    return false

}

我正在寻找使用上面列出的约束编写代码的帮助。任何帮助，将不胜感激。

Answer 1

您可以使用按位运算符。由于年龄限制为最大 50，因此只有 25 个不同的对，其中一个是另一个的两倍：(0, 0), (1, 2), ... (25, 50)。这 25 种可能性中的每一种都可以是（32 位）整数中的一位。您可以使用一个整数来标记您遇到的年龄介于 0 到 25 之间的位（对于该对的第一部分），并使用另一个整数来标记您遇到偶数年龄的位：您将首先将年龄减半，然后设置相应的位。当这两个整数有一个共同的位集时，答案是肯定的。这是一个逻辑与。有一种特殊情况：0 的双倍是 0，所以如果我们遇到单个 0，那么两个整数的第一位都会被设置为 1。但要求是有“另一个”具有双倍年龄的人，所以这会产生误报。所以，解决方案是区别对待 0，只计算你是否有两个。这是 JavaScript 中的一个实现：function isPersonTwiceOldAsOthers(persons) {&nbsp; &nbsp; let smalls = 0, halves = 0, numZeroes = 0;&nbsp; &nbsp; for (let age of persons) {&nbsp; &nbsp; &nbsp; &nbsp; if (age == 0) numZeroes++;&nbsp; &nbsp; &nbsp; &nbsp; if (age > 0 && age <= 25) smalls |= (1 << age);&nbsp; &nbsp; &nbsp; &nbsp; if (age > 0 && (age & 1) == 0) halves |= (1 << (age >> 1));&nbsp; &nbsp; }&nbsp; &nbsp; return numZeroes > 1 || (smalls & halves) != 0;}// Demolet res;res = isPersonTwiceOldAsOthers([4, 9, 34, 12, 18, 37]);console.log(res); // trueres = isPersonTwiceOldAsOthers([4, 7, 34, 12, 18, 37]);console.log(res); // falseres = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 37]);console.log(res); // falseres = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 0]);console.log(res); // true注意：在 C 类型和许多其他语言中，代码行数是主观的。在 Go 中，它可能看起来像这样：func isPersonTwiceOldAsOthers(person []int) bool {&nbsp; &nbsp; var smalls, halves, numZeroes int;&nbsp; &nbsp; for _, age := range person {&nbsp; &nbsp; &nbsp; &nbsp; if age == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; numZeroes++;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if age > 0 && age < 26 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; smalls |= (1 << age);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if age > 0 && (age & 1) == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; halves |= (1 << (age >> 1));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return numZeroes > 1 || (smalls & halves) != 0;}func main() {&nbsp; &nbsp; res := isPersonTwiceOldAsOthers([]int{4, 9, 34, 12, 18, 37});&nbsp; &nbsp; println(res); // true&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; res = isPersonTwiceOldAsOthers([]int{4, 7, 34, 12, 18, 37});&nbsp; &nbsp; println(res); // false&nbsp; &nbsp; res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 37});&nbsp; &nbsp; println(res); // false&nbsp; &nbsp; res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 0});&nbsp; &nbsp; println(res); // true&nbsp;&nbsp;}