如何在不使用运算符和映射或使用 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) {

    let smalls = 0, halves = 0, numZeroes = 0;

    for (let age of persons) {

        if (age == 0) numZeroes++;

        if (age > 0 && age <= 25) smalls |= (1 << age);

        if (age > 0 && (age & 1) == 0) halves |= (1 << (age >> 1));

    }

    return numZeroes > 1 || (smalls & halves) != 0;

}

// Demo

let res;

res = isPersonTwiceOldAsOthers([4, 9, 34, 12, 18, 37]);

console.log(res); // true

res = isPersonTwiceOldAsOthers([4, 7, 34, 12, 18, 37]);

console.log(res); // false

res = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 37]);

console.log(res); // false

res = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 0]);

console.log(res); // true

注意：在 C 类型和许多其他语言中，代码行数是主观的。

在 Go 中，它可能看起来像这样：

func isPersonTwiceOldAsOthers(person []int) bool {

    var smalls, halves, numZeroes int;

    for _, age := range person {

        if age == 0 {

            numZeroes++; 

        }

        if age > 0 && age < 26 {

            smalls |= (1 << age);

        }

        if age > 0 && (age & 1) == 0 {

            halves |= (1 << (age >> 1));

        }

    }

    return numZeroes > 1 || (smalls & halves) != 0;

}

func main() {

    res := isPersonTwiceOldAsOthers([]int{4, 9, 34, 12, 18, 37});

    println(res); // true

    

    res = isPersonTwiceOldAsOthers([]int{4, 7, 34, 12, 18, 37});

    println(res); // false

    res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 37});

    println(res); // false

    res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 0});

    println(res); // true  

}