二进制展开式中含有 n 个 1 的第 k 个数的恒定时间算法

问题描述 投票:0回答:1

我正在寻找一种算法,可以在恒定的时间内有效地找到其二进制展开式中恰好有 n 个 1 的第 k 个数字。 (按升序排列数字)。

例如,如果 k = 3 且 n = 2: 二进制展开式中含有 2 个 1 的数字是: [0b11、0b101、0b110、0b1001、...] 因此答案是 0b110 = 6.

到目前为止,我只想到了蛮力方法,在一定范围内创建 1 和 0 的所有可能排列(恰好有 n 个 1),对结果进行排序并提取第 k 个值。

我不完全确定是否存在恒定时间解决方案,但我确信有比我现有的更好的解决方案。

python algorithm sorting optimization
1个回答
0
投票

我不会为你编写代码。但这是总体思路。

你可以问:正好有

n
1 的
n
位数字有多少个。 [提示,正好 1。]。有多少个
n+1
位数字恰好是
n
1。 [
n-1
,因为 0 可以去任何地方,除了第一个数字。您可以继续查看,有
choose(q-1, k-1)
q
位数字,并且恰好有
k
个数字。

所以你明白了

  1. 多大
    q
    ,答案的长度是,
  2. 长度减去长度
    q
    的长度恰好有
    k
    1 秒。称之为
    p
  3. 所以你需要找到第
    n-p
    q
    位且正好
    k
    1 秒的数字。

您知道答案的第一位数字是

1
。第二个数字是零还是一?计算该位置有多少个 0 和 1。继续计算,直到计算出整个值。

细节有点棘手,您需要确保计数准确。但你可以得到答案是log(n)。

© www.soinside.com 2019 - 2024. All rights reserved.