Algo(0) Majority-Element

¶开始

最近想出来一个好主意，因为最近也在学习上算法课，打算把学校学了的算法课用在LeetCode刷题当中。

我现在都还在想是用中文写作还是英文写作方便一些呢。最后觉得 普通日常部分主要用中文，代码方面的话中英夹杂的情况肯定比较多。

那先来第一题吧，正好这道题是这星期465作业的一道题，用Divide and Conquer 解 Majority element

地址： Majority Element

¶题目

¶Leetcode 描述

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

Input: nums = [3,2,3]
Output: 3
Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2
 

Constraints:

n == nums.length
1 <= n <= 5 * 104
-231 <= nums[i] <= 231 - 1

¶作业描述

(16 pts.) Divide-and-Conquer An array A[1…n] is said to have a majority element if more than half of its entries are the same.

Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form “is A[i] > A[ j]?” (Think of the array elements as GIF files, say.) However you can answer questions of the form: “is A[i] = A[ j]?” in constant time.

Design a dynamic programming algorithm to solve this problem in O(nlogn) time. You may assume that n is a power of two. (Hint: the divide step is simple: just split the array into the left half and right half. How does knowing the majority elements (if they exist) of the two halves help you figure out the majority element in the whole array? Consider all the possibilities.)

1. Describe the algorithm, either in pseudo-code or English.

2. Argue why your algorithm is correct

3. Do a running time analysis of your algorithm.

¶想法

作业中已经提到提出一个 $O(nlogn)$ 时间的算法，且提到了 把 array 等分两份，即$T(n) = 2(T/2)+O(?)$ ，In worst case, if ?=n, the algorithm will be $T(n) = 2(T/2) + O(n)$， 用master theorem， 就能得到 $O(nlogn)$.

此题的重点在于如果已知 两个part是否已经有me（majority element）能不能帮助得到整块的majority element。一旦把所有的case想清楚，那么这道题就迎刃而解了。

¶算法 (并非最优解)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        leng = len(nums);
        return self.maj(nums, 0, leng);
    
    def maj(self, nums, left, right):
        if(right-left ==1):
            return nums[left];
        else:
            x= self.maj(nums, left, (left+right)//2);
            y= self.maj(nums, (left+right)//2, right);

            if(x==y):
                return x;
            elif(x!=y):
                return x if (nums[left:right+1].count(x) > nums[left:right+1].count(y)) else y;
            elif(x == None and y != None):
                return y;
            elif(y == None and x != None):
                return x;
                

¶反思

• 做作业时候觉得就不简单（好吧其实这是 leetcode 简单级别的题目，主要还是我太菜了 😢 ）因为作业已经要求用divide and conquer 做，所以我也是直接把作业 的pseudo-code 转化成了python（一开始用java 一直编译失败，索性换成python吧 😂 ）。
• 需要熟悉 平台 回答界面的接口，特别是java。
• 需要了解解题时候允许的库。

第一次提交leetcode 的 结果：

😂 万事开头难，加油！