• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            一列1-n的數(shù),其中有一個重復的(意味著有一個數(shù)missing),找出重復了一次的數(shù)以及缺少的那個數(shù)

            思路一:開個dict存每個數(shù)出現(xiàn)幾次,再掃一遍找出duplicate和missing
             1 #645
             2 #Runtime: 447 ms
             3 #Memory Usage: 15.5 MB
             4 
             5 class Solution(object):
             6     def findErrorNums(self, nums):
             7         """
             8         :type nums: List[int]
             9         :rtype: List[int]
            10         """
            11         dict_num = {}
            12         ans = [0, 0]
            13         for i in nums:
            14             if i not in dict_num:
            15                 dict_num[i] = 1
            16             else:
            17                 dict_num[i] += 1
            18         for i in range(1, len(nums) + 1):
            19             if i not in dict_num:
            20                 ans[1] = i
            21             elif dict_num[i] > 1:
            22                 ans[0] = i
            23         return ans

            思路二(看solution得到的啟發(fā),不使用其他dict等多余存儲):第一遍掃的時候?qū)⑽挥趎ums[abs(nums[i]) - 1]的數(shù)*-1,發(fā)現(xiàn)某個數(shù)已經(jīng)是負的話說明duplicate,第二遍再掃一次,找出仍然大于0的數(shù),其對應的下標就是missing的那個
             1 #645
             2 #Runtime: 495 ms
             3 #Memory Usage: 14.2 MB
             4 
             5 class Solution(object):
             6     def findErrorNums(self, nums):
             7         """
             8         :type nums: List[int]
             9         :rtype: List[int]
            10         """
            11         ans = [0, 0]
            12         for i in range(len(nums)):
            13             if nums[abs(nums[i]) - 1] < 0:
            14                 ans[0] = abs(nums[i])
            15             else:
            16                 nums[abs(nums[i]) - 1] *= -1
            17         for i in range(len(nums)):
            18             if nums[i] > 0:
            19                 ans[1] = i + 1
            20         return ans

            思路三(看solution得到的啟發(fā),異或思想,只用一重for循環(huán),但需要一個dict):原理:a^b^b=a
             1 #645
             2 #Runtime: 471 ms
             3 #Memory Usage: 15.7 MB
             4 
             5 class Solution(object):
             6     def findErrorNums(self, nums):
             7         """
             8         :type nums: List[int]
             9         :rtype: List[int]
            10         """
            11         dict_num = {}
            12         ans = [0, 0]
            13         for i in range(len(nums)):
            14             if nums[i] not in dict_num:
            15                 dict_num[nums[i]] = 1
            16             else:
            17                 ans[0] = nums[i]
            18                 dict_num[nums[i]] += 1
            19             ans[1] ^= (i + 1)
            20             ans[1] ^= nums[i]
            21         ans[1] ^= ans[0]
            22         return ans

            思路四(看solution得到的啟發(fā),異或思想,但實際只需要三重for循環(huán),不需要額外dict),原理:a^b^b=a,找出a和b二進制最后一位出現(xiàn)不同的位置,將1-n分為兩類,掃一遍nums和1-n之后,在其中一類會出現(xiàn)a,另一類出現(xiàn)b^b^b(=b),再掃一次nums就能找到b位于哪一類
             1 #645
             2 #Runtime: 306 ms
             3 #Memory Usage: 14.8 MB
             4 
             5 class Solution(object):
             6     def findErrorNums(self, nums):
             7         """
             8         :type nums: List[int]
             9         :rtype: List[int]
            10         """
            11         ans = [0, 0]
            12         xor = 0
            13         for i in range(len(nums)):
            14             xor ^= (i + 1)
            15             xor ^= nums[i]
            16         rightmostbit = xor & ~(xor - 1)
            17         for i in range(len(nums)):
            18             if (i + 1) & rightmostbit != 0:
            19                 ans[1] ^= (i + 1)
            20             else:
            21                 ans[0] ^= (i + 1)
            22             if nums[i] & rightmostbit != 0:
            23                 ans[1] ^= nums[i]
            24             else:
            25                 ans[0] ^= nums[i]
            26         for i in nums:
            27             if ans[0] == i:
            28                 return ans
            29         return [ans[1], ans[0]]
            97久久国产露脸精品国产| 久久久久久久综合日本亚洲 | 日韩人妻无码精品久久久不卡| 精品久久久久久久无码| 久久综合88熟人妻| 精品久久久久久国产免费了| 亚洲va久久久久| 久久久老熟女一区二区三区| 国产亚洲精久久久久久无码AV| 久久久久亚洲精品日久生情| 久久久久久综合一区中文字幕| 亚洲人AV永久一区二区三区久久| 99麻豆久久久国产精品免费| 亚洲伊人久久成综合人影院 | 国产精品久久久久久久app| 97久久超碰成人精品网站| 少妇被又大又粗又爽毛片久久黑人| 色狠狠久久AV五月综合| 国产99久久久国产精品小说| 伊人久久免费视频| 国产精品美女久久久m| 伊人久久大香线蕉av不卡| 久久久久黑人强伦姧人妻| 精品久久久久久国产91| 久久久无码人妻精品无码| 色综合久久夜色精品国产| 久久97久久97精品免视看| 久久99国产精品久久久| 久久er99热精品一区二区| 久久精品国产亚洲AV久| 久久免费99精品国产自在现线 | 精品一区二区久久久久久久网站| 一级做a爰片久久毛片毛片| 国产亚洲色婷婷久久99精品91| 99久久精品国产高清一区二区| 久久久国产乱子伦精品作者| 狠狠精品久久久无码中文字幕| 国产A级毛片久久久精品毛片| 久久夜色精品国产噜噜亚洲a| 狠狠色丁香婷婷久久综合五月| 久久这里有精品视频|