Home 成长之路 Leetcode题解 数组之有序数组

数组之有序数组

给你一个非递减的 有序 整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例:
输入:arr = [1,2,2,6,6,6,6,7,10]
输出:6
解题思路:注意该数组为有序数组,且只有一个符合要求的整数;
方法一:双指针法
  1. 数组有序,且某元素出现次数超过25%
  2. 那么对于此元素第1次出现位置,加25%数组长度,必定仍为它自身

int findSpecialInteger(int* arr, int arrSize) {

    for (int *p = arr, *q = arr + arrSize / 4; ; p++, q++)//有序,若出现次数超过25%,则arr[i]=arr[i+arrSize/4];
        if (*p == *q) return *p;
    return 0;  
}
方法二:遍历
int findSpecialInteger(int* arr, int arrSize){
//int len = arrSize/4;
int i = 1,cou = 0;
int temp = arr[0];
    while(i < arrSize){
if(temp == arr[i]){
cou++;
            if(cou*4 >= arrSize){
                break;
            }
        }
        else{
            cou = 0;
        }
        temp = arr[i];
        i++;//在一次循环中进行移动;
    }
    return temp;
}
方法三:二分查找
对于此题来说二分查找无意义,故不讨论;

SIMILAR ARTICLES

0 8

0 9

发表评论

发表评论