题目描述

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

代码一

思想:简单暴力的遍历,时间复杂度为n

  1. int count = 0;
  2.         for(int i=0;i<array.length;i++)
  3.        {
  4.            if(array[i]==k)count++;
  5.        }
  6.         return count;
  7.     }

代码二

思想:
从两头同时找时间复杂度n/2**

  1. public int GetNumberOfK(int [] array , int k) {
  2.        int i=0;
  3.        int j=array.length-1;
  4.        int count=0;
  5.        while(i<=j)
  6.        {
  7.            if(i==j&&array[i]==k){
  8.                count++;
  9.                break;
  10.            }
  11.            if(array[i]==k)count++;
  12.            if(array[j]==k)count++;
  13.            i++;
  14.            j--;
  16.        }
  17.        return count;
  18.     }

代码三