【LeetCode】 169. 多数元素 2020年3月13日

红太狼 2021-06-10 20:38 369阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

题目得时间复杂度肯定不小于n，所有得元素必须要遍历一遍之后才能知道结果

1.  比较简单想到的就是 `哈希表`，存储好当前得值出现得次数即可，时间复杂度为 `O(n)` ，空间复杂度也为 `O(n)`
2.  因为题目给出了务必有这个数字，所以先排序再取 `n/2` 处得值即为所求，时间复杂度为 `O(nlogn)`，空间复杂度为 `O(1)`

### code ###

#### solution1 ####

class Solution { 
        public int majorityElement(int[] nums) { 
            if(nums.length==1) return nums[0];
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            for (int num : nums) { 
                if (hashMap.containsKey(num)) { 
                    int temp = hashMap.get(num);
                    if (++temp > nums.length / 2) return num;
                    else hashMap.put(num, temp);
                } else { 
                    hashMap.put(num, 1);
                }
            }
            return -1;
        }
    }

#### solution2 ####

class Solution { 
        public int majorityElement(int[] nums) { 
            Arrays.sort(nums);
            return nums[nums.length/2];
        }
    }

[Link 1]: https://leetcode-cn.com/problems/majority-element/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/e186292152d941118c0c055e2149bfa0.png