我正在寻找一种算法,可以在恒定的时间内有效地找到其二进制展开式中恰好有 n 个 1 的第 k 个数字。 (按升序排列数字)。
例如,如果 k = 3 且 n = 2: 二进制展开式中含有 2 个 1 的数字是: [0b11、0b101、0b110、0b1001、...] 因此答案是 0b110 = 6.
到目前为止,我只想到了蛮力方法,在一定范围内创建 1 和 0 的所有可能排列(恰好有 n 个 1),对结果进行排序并提取第 k 个值。
我不完全确定是否存在恒定时间解决方案,但我确信有比我现有的更好的解决方案。
我不会为你编写代码。但这是总体思路。
你可以问:正好有
n
1 的 n
位数字有多少个。 [提示,正好 1。]。有多少个 n+1
位数字恰好是 n
1。 [n-1
,因为 0 可以去任何地方,除了第一个数字。您可以继续查看,有 choose(q-1, k-1)
q
位数字,并且恰好有 k
个数字。
所以你明白了
q
,答案的长度是,q
的长度恰好有 k
1 秒。称之为p
。n-p
个 q
位且正好 k
1 秒的数字。您知道答案的第一位数字是
1
。第二个数字是零还是一?计算该位置有多少个 0 和 1。继续计算,直到计算出整个值。
细节有点棘手,您需要确保计数准确。但你可以得到答案是log(n)。