leetcode Map

leetcode 169题

Posted by franki on August 28, 2021

leetcode 169题 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

思路

方法1：投票法

方法2：map

代码

// vote
function majorityElement(nums) {
  let res = nums[0], count = 0;

  for (let i=0; i<nums.length; i++) {
    if (count === 0) {
      res = nums[i];
      count = 1;
    } else {
      if (res === nums[i]) {
        count++;
      } else {
        count--;
      }
    }
  }
  return res;
}

// map
function majorityElement(nums) {
    const map = new Map();

    for (let num of nums) {
        if (map.has(num)) {
            map.set(num, map.get(num)+1);
        } else {
            map.set(num, 1);
        }
        if (map.get(num) > Math.floor(nums.length / 2)) {
            return num;
        }
    }

    return 0;
}

复杂度分析

方法1：

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)

方法2：

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS