爲3 * num設置的位數，包含一個列表o設置num位的位位置

假設您有一個數組，其中包含一個非常大的數字（高達10000位，不能用基元表示類型）。例如：array：[0,2,3,6,10]對應於10001001101.爲3 * num設置的位數，包含一個列表o設置num位的位位置

換句話說：num = pow（A [0]）+ pow（A [1]）+ .... + pow（A [n-1]），其中pow（x）= 2 ^x。

現在假設你有一個數字K = 3 * num。

如何查找K中設置的位數？

我相信有可能在O（n）中做到這一點，其中n是數組中元素的數量。

我的想法是遍歷數組中的項目，模擬數字和本身之間的添加向左移動1個位置。但是我找不到一個乾淨的邏輯。

來源

2016-11-20 Marcus

IMO直覺是正確的：從正確的工作（LSB）到左（MSB），而加入攜帶。 – wildplasser

這正是我的想法，但它有點棘手。考慮數字5 - 數組是[0，2]。結果你應該得到4。然後考慮7 - 數組是[0，1，2]，結果爲3. – Marcus

我想澄清。如果num = 5（arr5 = [0,2]，是3 * 5 = 15（arr15 = [0,1,2,3]）你想要什麼？ – Ripi2

從LSB到MSB的工作，您有運行的設置位被清除位的運行分隔：間隙。
（沒有攜帶在）每個單1會變成 11 - 「多顯著 1」在那裏有個地方一個零之前：沒有 進行了。
如果您將10添加到長期運行的1 s並清除最不重要的位，您將得到原始數字的三倍的二進制表示 - 具有完全相同的位數設置。並且1其中可能是是下一個，err，以及1：a 進位進出。任何進行 in被吸收：它只是「交換」最低有效位。
與表示三次單個 1的11，一個攜帶在導致攜帶出 - 並清除兩個比特（嘗試用101011 * 3）。
長度超過一個「吸收」的間隙進行。
假設輸入指數按照升序排序，或者用O（n）算法使我驚喜。我很想用標籤來編寫一個狀態機。
因爲我練的Python：

def popcount3num(indices): 
    ''' 
    given, in (strictly) ascending order, the indices of bits set 
    in the binary representation of a natural number num, 
    return the number of bits set in 3*num 
    ''' 
    prev = -3   # position of last bit handled 
    count = carry = 0 # carry is for bitposition handled + 2 
    for i in indices: 
    # print(i, count, carry) 
     if prev == i-1:  # in a run of set bits 
      if not carry: 
       carry = 1 # "move bit from count to carry" 
       count -= 1 
      else: 
       count += 1 # tally 
     else:    # gap 
      if not carry: 
      # without a carry in, every run produces 
      # two bits at least, including carry out 
       count += 2 
      elif prev < i-2: 
      # if the carry was for a lower position, just tally 
       count += 3 
       carry = 0 
      else: 
      # with a carry in, a lone one will change nothing 
      # a run will add just as many as without carry 
       pass 
     prev = i 
    return count + carry

來源

2016-11-21 00:38:15 greybeard

我看到挑戰的地方表明它比這更簡單。它不提供解決方案，但是說O（n）運行時，O（1）空間。 – Marcus

@Marcus：給定的索引按升序排列，這個_是O（n）_（並且很簡單，至少有一些）。使用任意順序的索引（你在這個問題的修訂版本1中沒有指定），如果有一種方法來確定_o（n）_中_3 * num_中設置的位數，我會感到驚訝。 – greybeard

有趣的解決方案。非常感謝並且很抱歉，很長時間以來我們都會回答。 – Marcus

從這個測試：

我觀察：

如果的sizeof（arrN）== 1，那麼的sizeof（ arrRes = 2
如果'v'存在於arrN和arr2N中，則將其消除並以'v + 1'重複，直到'v + x'不存在或是最後的價值。然後增加'v + x'。例子N = 3：兩者都存在'1'，消除; '2'只在一個，但是最後;增加'2'。
應用2）如果一個值存在於arrN中，但不在arr2N中，那麼它將存在於arrRes中，大小將爲++ 1。對於arr2N中的值而不是arrN中的值相同。例子N = 9。

N = 11是一個複雜的例子。詳細說明：

'arrN'中的'0'，而不是arr2N，所以放在arrRes中。
「1」in both;跳過「1」並測試1 + 1 = 2。
'2'in both（well，really only in arr2N，we made the fake'2'from other arr），skip and test'3'。
arrN中內置的'3'存在於arrN中。跳過並測試'4'。
'4'存在是最後一個。增加它。
最終結果[0,5]： '0' 從步驟1和 '5' 從步驟5

來源

2016-11-21 02:01:35 Ripi2

對於一般情況res = num1 * num2，我相信可以找到一個O（n）算法，因爲num1 =一些移位（它只增加arrNum2中的值）和+ num1（如果！= 0）適用於我的觀測。 – Ripi2

你的方法似乎有效。但我仍然認爲可以在O（n）運行時和O（1）空間中執行此操作。 – Marcus

讓我問，爲什麼你需要這麼複雜的任務？我會將一個大的二進制表示分成小塊，比如32位塊。總和和乘法可以用這些小塊來定義，比使用數組快得多。 – Ripi2

爲3 * num設置的位數，包含一個列表o設置num位的位位置

回答

相關問題