來找獨特數啊

本博客第一篇文章的誕生特別鳴謝ly同學的激勵與幫助

異或運算

1. 異或運算是位運算，簡言之即相同為0，不同為1
2. 在數學表達中用 ⊕ 符號表示異或，在計算機中用 ^ 符號代表異或運算
3. 任何數與自己異或為0，a ^ a = 0
4. 任何數與0異或等于自己，a ^ 0 = a
5. 異或運算具有交換律，a ^ b ^ a=a ^ a ^ b=b

產生測驗所用的串列代碼

import random as rd


def product_list(n, odd_num):
    """
    :param n:產生多少對亂數
    :param odd_num: 產生幾個奇異數
    :return:
    """
    demo_list = rd.sample(range(100), n)  # randsample會產生n個[0,100)互不相同的亂數
    demo_list.extend(demo_list)  # 我擴展我自己，這樣demo_list中就有n對相同的亂數了
    demo_list.append(rd.randint(1000, 2000))
    print('odd1 = %d' % demo_list[n * 2])
    if odd_num == 2:
        demo_list.append(rd.randint(2000, 3000))
        print('odd2 = %d' % demo_list[n * 2 + 1])
    elif odd_num == 3:
        demo_list.append(rd.randint(2000, 3000))
        print('odd2 = %d' % demo_list[n * 2 + 1])
        demo_list.append(rd.randint(3000, 4000))
        print('odd3 = %d' % demo_list[n * 2 + 2])
    return demo_list

101個數中，有50對數相同，有1個數為奇異數，找出該奇異數

• 由上述異或性質5,3，可將101個數重新排列為相同的數相鄰，最后一位為奇異數，將陣列從頭異或至尾，即可得到該奇異數

def find_1odd(demo_list):
    odd = 0
    for element in demo_list:
        odd ^= element
    return odd

102個數中，有50對數相同，有2個數為奇異數，找出奇異數

• 這里要引出分堆器的思想，也是代碼思想中常用的分而治之的思想，如何產生一個分堆器將兩個奇異數分到兩堆之中，進而可以直接利用上面的find_1odd?

  • 這里先講方法，具體思想可參考博客12. 【C語言】 102個整數中有50個數出現了兩次，2個數出現了一次， 找出出現了一次的那2個數（2_task）_DennisCheng520的博客-CSDN博客
  • 就是利用find_1odd先得到初始分堆器divider，由于異或性質5,3，這個divider其實就是那兩個奇異數異或的結果
  • 之后divider = divider & (-divider)才會得到真正的分堆器，這個分堆器中只有1位為1，剩余位全是0，而兩個奇異數的對應的這一位恰巧一位為0，一位為1，
  • 至此，根據divider與串列中元素相與的結果是否為0，就可將原來的串列分為兩堆，再對這兩堆分別利用find_1odd，即可得到兩個奇異數

  def find_2odd(demo_list):
      # divider可翻譯為分堆器,這里只是初始分堆器
      divider = find_1odd(demo_list)
      # 這里生成了真正的分堆器，分堆器根據串列中元素某一位為0或1將串列分為兩堆，兩個奇異數會被分開
      divider = divider & -divider
      list0, list1 = [], []
      for element in demo_list:
          if divider & element == 0:
              list0.append(element)
          # elif:divider&element==1: 這一句的使用是錯誤的，思考為什么？
          else:
              list1.append(element)
      odd0 = find_1odd(list0)
      odd1 = find_1odd(list1)
      return odd0, odd1
  

103個數中，有50對數相同，有3個數為奇異數，找出奇異數

• 這里同樣要利用分堆的思想，將三個奇異數分為兩堆，一堆含有一個奇異數，另一堆含有另外兩個奇異數，
• 因為尚未找到巧妙的方法直接找到分堆器，因此這里使用暴力破解的方法，利用回圈左移，依次使用1,10,110,1110,11110…這些分堆器，來對串列進行分堆，
• 但這有一個小坑就是可能當前使用的分堆器1所在的位對應的三個奇異數的那位相同，此時三個奇異數會被分到一堆，也就無法找出奇異數了，
• 因此在分堆之后，分別對兩堆異或的結果進行監測，若兩分堆異或的結果均不為0，即可使用find_1odd和find_2odd正確找到奇異數

def find_3odd(demo_list):
    divider = 1
    result = [0] * 3
    for i in range(32):  # 暴力使用32個分堆器:1,10,100,1000...
        list0 = []
        list1 = []
        for element in demo_list:
            if element & divider == 0:
                list0.append(element)
            else:
                list1.append(element)
        result0 = find_1odd(list0)
        result1 = find_1odd(list1)
        if result0 != 0 and result1 != 0:
            if len(list0) % 2 == 1:
                result[0] = result0
                result[1], result[2] = find_2odd(list1)
                break
            elif len(list1) % 2 == 1:
                result[0]= result1
                result[1],result[2] = find_2odd(list0)
                break
        divider <<= 1  # 分堆未成功，則使用新的分堆器
    return result

效果演示

if __name__ == '__main__':
    demo_list = product_list(50, 3)
    result = find_3odd(demo_list)
    print(result)