# Majority Element

## Question

**Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.**

You may assume that the array is non-empty and the majority element always exist in the array.

## Answer

### solution：

```python
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        record = {}
        for i in xrange(len(nums)):
            if nums[i] not in record:
                record[nums[i]] = 1
            else:
                record[nums[i]] += 1
        for i in record:
            if record[i] > len(nums)/2:
                return i
```

## Knowledge：

1. 可能这个算法并不是最佳的复杂度，但是终究能解决问题。此外，还在本地进行调试，从而帮助了这个程序。
2. 字典的遍历方法：

   ```python
    l = [(x,x) for x in xrange(10000)]
    d = dict(l)

    from time import clock

    t0=clock()
    for i in d:
        t = i + d[i]
    t1=clock()

    for k,v in d.items():
        t = k + v
    t2=clock()

    for k,v in d.iteritems():
        t = k + v
    t3=clock()

    print t1-t0, t2-t1, t3-t2
   ```

   结果为 `0.00184039735833 0.00326492977712 0.00214993552657`，可见第一种方法速度最快。第二种方法的记忆方式为key，value在items中。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmy-walker.gitbook.io/leetcode-training/array/majority-element.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.