欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数字在排序数组中出现的次数(Java)

程序员文章站 2024-03-20 12:51:34
...

题目:

统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3,由于3在这个数组中出现了4次,因此输出4。

思路:

第一种解法:蛮力法,顺序遍历数组,统计出数字3出现的次数,不过这时就没有利用到题目中给的有序,故时间复杂度过大,不符合要求。

第二种解法:利用二分查找的思想(时间复杂度log(n))来解决问题。首先先找到数组中3出现的第一个位置first3,然后再找到数组中3最后一次出现的位置end3,first3 - end3 + 1就是数字3出现的次数。

代码实现:

public class Main {

	//找出第一个k的位置
	private int getFirstK(int nums[], int k, int start, int end){
		if(start > end){
			return -1;
		}
		int middleIndex = (start + end) /2;
		int middleData = nums[middleIndex];
		if(middleData == k){
			//找出第一个位置k的终止条件:要么middleIndex=0;要么middleIndex > 0但是middleIndex-1处的位置不等于k
			if((middleIndex > 0 && nums[middleIndex-1]!=k) || middleIndex == 0){
				return middleIndex;
			}else{
				end = middleIndex -1;
			}
		}else if(middleData > k){
			end = middleIndex - 1;
		}else{
			start = middleIndex + 1;
		}
		return getFirstK(nums, k, start, end);
	}
	
	//找出最后一个k的位置
	private int getLastK(int nums[], int k, int start, int end){
		if(start > end){
			return -1;
		}
		int middleIndex = (start + end) / 2;
		int middleData = nums[middleIndex];
		if(middleData == k){
			//找出最后一个位置k的终止条件:要么middleIndex=长度-1;要么middleIndex < len-1但是middleIndex+1处的位置不等于k
			if((middleIndex < nums.length -1 && nums[middleIndex + 1] != k) || middleIndex == nums.length -1){
				return middleIndex;
			}else{
				start = middleIndex + 1;
			}
		}else if(middleData < k){
			start = middleIndex + 1;
		}else{
			end = middleIndex -1;
		}
		return getLastK(nums, k, start, end);
	}
	
	public int getNumberOfK(int nums[], int k){
		int number = 0;
		int len = nums.length;
		if(nums != null && len > 0){
			int firstK = getFirstK(nums, k, 0, len-1);
			int lastK = getLastK(nums, k, 0, len-1);
			if(firstK > -1 && lastK > -1){
				number = lastK - firstK + 1;
			}
		}
		return number;
	}
	
	public static void main(String[] args) {
		Main m1 = new Main();
		int nums[] = new int[]{1, 2, 3, 3, 3, 3, 4, 5};
		int count = m1.getNumberOfK(nums, 3);
		System.out.println(count);
	}
}