数字在排序数组中出现的次数

本贴最后更新于 2230 天前,其中的信息可能已经事过境迁

题目描述

统计一个数字在排序数组中出现的次数。

解题思路

题目中已经说明是排序数组,所以可知数组是非递增或者非递减的。

  • 利用 increase 标志保存数组非递增或非递减;

  • 遍历数组:

    • 如果与 K 相等,则 ret++;

    • 如果在 increase 标志下,已经越过了数字 k 的界限,则 break。

判断是否越过了数字 k 的界限是通过 异或 判断,

  • 如果 increase=true,说明是非递减序列,如果 array[i] <= k 是 false,说明此时 array[i]>k,经过异或就是 true;

  • 如果 increase=false,说明是非递增序列,如果 array[i] <= k 是 true,经过异或还是 true。

代码

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if (array == null || array.length == 0)
           return 0;
        int ret = 0;
        boolean increase = array[0] <= array[array.length-1];
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k)
                ret++;
            if ((array[i] <= k) ^ increase)
                break;
        }
        return ret;
    }
}

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...