劍指offer53~在排序數組中查找數字

The Amount Of A Certain Character In Sorted Array

Description

統計一個數字在排序數組中出現的次數。例如，輸入排序數組{1,2,3,3,3,3,4,5}和數字3，由于3在這個數組中出現了4次，是以輸出4.

Solution

• 方法一：暴力搜尋

在O（n）的時間内便利，統計這個數字出現的次數。

• 方法二：二分法定位數字出現的位置，按照大小關系，調整兩個指針的位置，利用遞歸循環調用自己來不斷進行修正，直至搜尋出。

Code

public class pointtooffer53 {
	public static int GetNumberOfk(int[]data , int k) {
		if(data==null||data.length==0)
			return -1;
		return min(data, k,0,data.length-1);
		
		
	} 
	public static int min(int []data,int k,int left,int right ){
		if(left>right)
			return 0;
		int mid=left+(right-left)/2;
		if(data[mid]>k)
			return min(data,k,left,mid-1);
		else if(data[mid]<k)
			return min(data,k,mid+1,right);
		else return 1+min(data,k,left,mid-1)+min(data,k,mid+1,right);
		//return 0;
		
	}
	
	public static void main(String[] args){
        int[] data1 = new int[]{1,2,3,3,3,3,5,6};
        int[] data2 = new int[]{1,2,3,3,3,3,4,5};
        int[] data3 = new int[]{3,3,3,3,3,3,3,3};
        System.out.println(GetNumberOfk(data1,4));
        System.out.println(GetNumberOfk(data2,3));
        System.out.println(GetNumberOfk(data3,3));

	}
	
	}

           

Appendix

1.和上一道11題目差不多，出不多的思路。雙指針，二分法；

2.注意mid-1賦給right，mid+1賦給left，不然下标會越界；

3.計算公式就是兩個1+小于号的+大于号的

4.遞歸簡單應用