LeetCode1287. 有序数组中出现次数超过25%的元素

80 views次阅读
一条评论

给你一个非递减的有序整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的25%。 请你找到并返回这个整数。

示例:

输入: arr = [1,2,2,6,6,6,6,7,10] 输出: 6

提示:
(1) 1 <= arr.lengthk <= 10^4
(2) 0 <= arr[i] <= 10^5

答案看这里哦👇

第一种方法,hash表,记录每个元素出现的次数,然后计算出现次数超过25%的元素

  const findSpecialInteger = (arr) => {
    if (arr.length &lt;= 3) return arr[0];
    let hasMap = {}, len = arr.length;
    for (let i = 0; i &lt; len; i++) {
      hasMap[arr[i]] = hasMap[arr[i]] !== undefined ? hasMap[arr[i]] + 1 : 1;
    }
    for (let k in hasMap) {
      if (hasMap[k] / len > 0.25) {
        return k;
      }
    }
  };
  const arr = [1,2,2,2,2,2,2,2,2,6,6,6,6,7,10];
  findSpecialInteger(arr); // 2

第二种方法优化: 一个for循环

  cosnt findSpecialInteger = (arr) =&gt; {
    if(arr.length &lt;= 3) return arr[0];
    let num = Math.ceil(arr.length * 0.25); // 返回一个比传入数字大的最小整数
    let num1 = 0;
    for(let i = 0; i &lt; arr.length - 1; i++) {
      arr[i] === arr[i + 1] ? num1++ : num1 = 0
      if (num === num1) {
        return arr[i]
      }
    }
  };

第三种方法: 使用filter,但是速度稍慢

获取同一元素的初始下标和最后下标,计算出对应元素所占用的数组长度

  const findSpecialInteger = arr =&gt; arr.length &lt;= 3 ? arr[0] : arr.filter(n =&gt; ((arr.lastIndexOf(n) - arr.indexOf(n) + 1) / (arr.length + 1) &gt;= 0.25))[0];

1
guxuerui
版权声明:本站原创文章,由guxuerui于2020年07月29日发表,共计1526字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(一条评论)
Loading...
骑誓 评论达人LV.1
2020-07-29 11:48:52 回复

还有更好的方法么