LeetCode #1287 Element Appearing More Than 25% In Sorted Array 有序数组中出现次数超过25%的元素

1287 Element Appearing More Than 25% In Sorted Array 有序数组中出现次数超过25%的元素

Description:
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example:

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Constraints:

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

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

请你找到并返回这个整数

示例 :

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

提示:

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

思路:

由于数组有序, 如果这个数是出现次数大于 25%的, 那么这个数和后面的 arr.size() / 4个数应该都是相等的, 按这个步长查找即可
时间复杂度O(n), 空间复杂度O(1)

代码:
C++:

class Solution 
{
public:
    int findSpecialInteger(vector<int>& arr) 
    {
        for (int i = 0, step = arr.size() / 4; i < arr.size() - step; i++) if (arr[i] == arr[i + step]) return arr[i];
        return arr[0];
    }
};

Java:

class Solution {
    public int findSpecialInteger(int[] arr) {
        for (int i = 0, step = arr.length / 4; i < arr.length - step; i++) if (arr[i] == arr[i + step]) return arr[i];
        return arr[0];
    }
}

Python:

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        return collections.Counter(arr).most_common(1)[0][0]
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • # 数组部分 # 1.## array_chunk($arr, $size [, $preserve_key = ...
    clothTiger阅读 1,412评论 0赞 1
  • 1.用js实现随机选取10~100之间的10个数字,存入一个数组,并排序 //要是获取不重复的,则对随机数...
    persistlu阅读 5,999评论 0赞 0
  • Ruby 数组(Array) Ruby 数组是任何对象的有序整数索引集合。数组中的每个元素都与一个索引相关,并可通...
    黑夜的眸阅读 1,244评论 0赞 0
  • 原创声明 本文系作者辛苦码字所得,欢迎分享和转载,但请在明显位置注明作者的如下信息:笔名:来碗鸡蛋面简书主页:ht...
    来碗鸡蛋面阅读 3,332评论 0赞 4
  • 大金国这些特聘武林高手的作派,杨康看在眼里,比在心里,对梅超风不由得多了几分敬重。 十五 应该说,在习武的起跑线上...
    弼马温孙行者阅读 1,398评论 0赞 2

友情链接更多精彩内容