LEETCODE 1287. Element Appearing More Than 25% In Sorted Array 解题思路分析

题目大意：

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

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例：

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

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1287

解题思路分析：

求一个元素的出现次数超过元素总数的25%，我们可以先求出总元素的25%是多少，然后再遍历整个数组，统计每种元素的个数，看哪个元素的个数大于25%即可。

实现代码：

public int findSpecialInteger(int[] arr) {
    float count = arr.length / 4f; // 总元素个数的四分之一
    int pre=arr[0]; // 首元素
    int length=0; // 连续相同元素的个数
    for(int n :arr){ // 循环每个元素
        if(n==pre){ // 如果当前元素与前元素相同
            // 连续相同个数加一
            // 如果连续相同个数大于总数的四分之一，返回当前元素
            if(++length>count) return n;
        }else{
            // 如果当前元素与前元素不同
            // 连续相同元素个数变为1（当前元素自身）
            length=1;
            // 将前元素更新为当前元素
            pre=n;
        }
    }
    return pre;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Element Appearing More Than 25% In Sorted Array.

Memory Usage: 39.6 MB, less than 100.00% of Java online submissions for Element Appearing More Than 25% In Sorted Array.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1287-element-appearing-more-than-25-in-sorted-array-解题思路分析/