pra*_*een 9 algorithm data-structures
我正在研究一个问题,在这个问题中,我希望得到数组中所有整数对的xor,然后找到从xor'ing产生的K个最小整数.阵列的大小可以是N = 100000,因此K可以非常大但限制为250000.
例如,如果N = 5且K = 4,
我们的阵列是 {1 3 2 4 2}
xoring(1和3,1-2,1-4,1-2,3-2,3-4,3-2等)产生的数字
3 3 2 5 0 1 6 1 6 7
由于K = 4,我们必须打印4个最小的整数.所以答案是0 1 1 2.
由于时间限制是2秒并且非常紧张,因此使用挖掘所有数字的强力方法会超时.我的做法是错的,所以我需要帮助.也许我们可以利用K = 250000的限制,并想知道是否有可能得到K个最小的数字而不用xoring所有的整数.
(x ^ y) == (x | y) - (x & y) >= |y - x|
按顺序对数字进行排序将是一个开始,因为对之间的差异将给出xor的下限,因此是何时停止寻找xor x的数字的截止点.
还有一个快捷方式寻找对数字,其异或小于(说)2的幂,因为你只能在X <= Y <= X感兴趣| (2 ^ N - 1).如果这没有给你足够的对,增加N并再试一次.
编辑:您当然可以通过使用x |排除已经找到的xor小于之前2的幂的数字对.(2 ^(N - 1) - 1)<y <= x | (2 ^ N) - 1.
基于(已排序)[1,2,2,3,4]的示例
首先查找xor小于1的数字对:对于每个数字x,搜索后续数字y = x.这给出了{2,2}.
如果你需要不止一对,找对数字,其异或小于2,但不低于1:每个数x,搜索数字X <Y <= X | 这给了{2,3}(两次).
请注意,最终的xor值未完全排序,但每个批次严格小于上一批次.
如果您需要更多,请查找xor小于4但不小于2的数字对:对于每个数字x,搜索数字x | 1 <y <= x | 这给出了{1,2}(两次); {1,3}.
如果您需要更多,请查找xor小于8但不小于4的数字对:对于每个数字x,搜索数字x | 3 <y <= x | 这给出了{1,4}; {2,4}(两次); {3,4}.