寻找具有两倍于其他元素的数组元素的简洁算法

欢迎各位小伙伴来到golang学习网，相聚于此都是缘哈哈哈！今天我给大家带来《寻找具有两倍于其他元素的数组元素的简洁算法》，这篇文章主要讲到等等知识，如果你对Golang相关的知识非常感兴趣或者正在自学，都可以关注我，我会持续更新相关文章！当然，有什么建议也欢迎在评论留言提出！一起学习！

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

以下是限制。

• 年龄是一个整数，取值范围为 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
}

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

解决方案

您可以使用按位运算符。

由于年龄限制为最大 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