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

题目描述

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

解题思路

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

• 利用 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;
    }
}