88. 合并兩個有序陣列

題目描述：給定兩個按非遞減順序排列的整數陣列nums1和nums2，另有兩個整數m，n，分別表示nums1和nums2中的元素數目，
請合并nums2到nums1中，使合并后的陣列同樣按非遞減順序排列，
注：最終函式不回傳合并后的陣列，而是存盤在陣列nums1中，為了應對這種情況，nums1輸入時，它的初始長度為m+n，其中前m項是nums1中的有效元素，后n個元素為0，例如，nums1=[1,2,3,0,0,0]，nums2=[1,2,3]；nums1=[4,5,6,7,0,0,0]，nums2=[1,2,3]，

1. 直接呼叫系統函式來進行排序

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2
        nums1.sort()

2. 雙指標

1）正序比較：
因為有兩個陣列，所以我們可以定義兩個指標，分別指向兩個陣列中的元素，最容易想到的就是從左到右（正序）依次比較，將較小元素放到前面，
注意，這里應該利用temp陣列來存盤資料，因為直接存放在nums1中的話，有可能會丟失資料，比如：nums1=[3,1,2,0,0]，num2=[1,2]，當p1=0，p2=0，因為nums1[p1] > nums2[p2]，所以我們應該把nums2[p2]換到nums1[p1]處，這樣nums1=[1,1,2,0,0]，這樣元素“3”就被覆寫了，所以需要一個另外的陣列來存盤資料，這樣就增加了額外的存盤空間，

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        sorted = []
        p1, p2 = 0, 0
        while p1 < m or p2 < n:
            if p1 == m: #p1結束了nums1的遍歷
                sorted.append(nums2[p2])
                p2 += 1
            elif p2 == n: #p2結束了nums2的便利
                sorted.append(nums1[p1])
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                sorted.append(nums1[p1])
                p1 += 1
            else:
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted

2）逆序比較
因為nums1陣列后面是“0”，所以如果從后面開始比較（nums1從最后一個有效元素開始），較大的數可以直接覆寫“0”放到nums1陣列的后面，
注意，這里的兩個陣列都是已經按非遞減順序排列好了的，

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m-1, n-1
        tail = m+n-1 #tail = len(nums1)-1
        while p2>=0:
            if p1 < 0 or nums1[p1] < nums2[p2]:
                nums1[tail] = nums2[p2]
                tail -= 1
                p2 -= 1
            else:
                nums1[tail] = nums1[p1]
                tail -= 1
                p1 -= 1

169.多數元素

題目描述：給定一個大小為n的陣列，找到其中的多數元素（陣列中出現次數大于n/2的元素），假設陣列非空，且給定的陣列總存在多數元素，
進階：嘗試設計時間復雜度為n，空間復雜度為1的演算法解決此問題，

1. 簡單思路（不滿足時間復雜度和空間復雜度）
首先對陣列進行排序，目的是為了讓相同元素排在一起，主要思想是記錄下原陣列中各個不同元素第一次出現的索引位置index，然后計算相鄰不同元素之間的距離，是否超過n/2，來判斷該元素是否為多數元素，不過執行結果超出了時間限制，說明這種方法不太高效，

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums)
        nums.sort()  #首先對陣列進行排序，重復的元素放在一起
        count = [0]
        p = 1   #p是指標，從nums第二個元素開始
        while p < l:    #存盤不同元素出現的第一個索引值
              if nums[p] != nums[p-1]:
                  count.append(p)
        count.append(l-1)   #將nums最后一個元素的索引值也存盤進來
        for i in range(l-1):
            if count[i+1]-count[i] >= len(nums)/2:
                break
        return nums[count[i]]

2. 秒殺方法
既然多數元素出現的次數大于n/2，說明陣列中間的元素一定是多數元素，（突然感覺自己像個傻x）

class Solution(object):
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]

3. Moore摩爾投票演算法
這里存在兩個重要因素，一個是candidate，一個是count，首先選取一個candidate，然后用count記錄candidate出現的次數，如果當前元素是candidate，count加一，反之count則減一，當count為0時，就把candidate設為當前數并繼續操作，
該演算法滿足時間復雜度n，空間復雜度1

class Solution(object):
    def majorityElement(self, nums):
        count = 0
        candidate = None

        n = len(nums)
        for i in range(n):
            if count == 0:
                candidate = nums[i]
            count += (1 if candidate == nums[i] else -1)

        return candidate

4. 字典方法（不滿足空間復雜度1）
利用字典存盤每個num，統計每個num出現的次數，回傳出現次數最多的num

class Solution(object):
    def majorityElement(self, nums):
        dic = defaultdict(int)
        #統計每個數字出現的次數
        for num in nums:
            dic[num] += 1
        #回傳出現次數最多的num, 即回傳字典中最大value對應的key
        return max(dic, key=dic.get)