【1】数字在数组中出现的次数

简介: 题目:统计一个数字k在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,输出4次 方案一:扫描数组,记录第一个出现的k和最后一个k中间有多少个,时间复杂度为O(n) 方案二:由于数组是有序的,那么我们可以利用二分的思想,求出k在数组中的第一个位置和最后位置相减即可。

题目:统计一个数字k在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,输出4次


方案一:扫描数组,记录第一个出现的k和最后一个k中间有多少个,时间复杂度为O(n)

方案二:由于数组是有序的,那么我们可以利用二分的思想,求出k在数组中的第一个位置和最后位置相减即可。时间复杂度为O(logN)

注意严格按照良好的C++编码风格


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

//规定没有找到返回-1
int GetFirstIndex(int *arrNum, int left, int right, int k){
	if(arrNum == NULL || left > right){
	    return -1;
	}
	while(left <= right){
	    int mid = (left+right)>>1;
		if(arrNum[mid] > k){
		    right = mid-1;
		}
		else if(arrNum[mid] < k){
		    left = mid+1;
		}
		else{
			if((mid > 0) && (arrNum[mid-1] == k)){
			    right = mid-1;
			}
			else{
			    return mid;
			}
		}
	}
	return -1;
}

//规定没有找到返回-1
int GetLastIndex(int *arrNum, int left, int right, int k){
	if(arrNum == NULL || left > right){
	    return -1;
	}
	while(left <= right){
	    int mid = (left+right)>>1;
		if(arrNum[mid] > k){
		    right = mid-1;
		}
		else if(arrNum[mid] < k){
		    left = mid+1;
		}
		else{
			if((mid < right-1) && (arrNum[mid+1] == k)){
			    left = mid+1;
			}
			else{
			    return mid;
			}
		}
	}
	return -1;
}

int main(){
	int arrNum[] = {1,2,3,3,3,3,4,5};
	//求出第一个和最后一个位置
	int firstIndex = GetFirstIndex(arrNum, 0, 7, 3);
	int lastIndex = GetLastIndex(arrNum, 0, 7, 3);
	if(firstIndex != -1 && lastIndex != -1){
	    cout<<(lastIndex-firstIndex+1)<<endl;
	}
	else{
	    cout<<-1<<endl;
	}
	return 0;
}


目录
打赏
0
0
0
0
15
分享
相关文章
|
10月前
给定 n 个整数,求里面出现次数最多的数,如果有多个重复出现的数,求值最大的那个 给定n个整数,求里面出现次数最多的数,如果有多个重复出现的数,求出值最大的一
给定 n 个整数,求里面出现次数最多的数,如果有多个重复出现的数,求值最大的那个 给定n个整数,求里面出现次数最多的数,如果有多个重复出现的数,求出值最大的一
|
10月前
|
PHP
在数组中,找出给定数字的出现次数,比如[1,2,3,2,2]中2的出现次数是3次(任意编程语言描述)
在数组中,找出给定数字的出现次数,比如[1,2,3,2,2]中2的出现次数是3次(任意编程语言描述)
60 0
|
5月前
计算字符串中子串出现的次数
【10月更文挑战第17天】计算字符串中子串出现的次数 。
41 3
|
8月前
计算字符串中子串出现的次数
【7月更文挑战第9天】计算字符串中子串出现的次数。
54 12
|
10月前
每日一题(づ ̄3 ̄)づ╭❤~(数字在升序数组中出现的次数,整数转换)
每日一题(づ ̄3 ̄)づ╭❤~(数字在升序数组中出现的次数,整数转换)
59 0
Day3 字符串中找出连续最长的数字串、数组中出现次数超过一半的数字
Day3 字符串中找出连续最长的数字串、数组中出现次数超过一半的数字
84 0
【剑指offer】-数字在排序数组中出现的次数-32/67
【剑指offer】-数字在排序数组中出现的次数-32/67
剑指offer 55. 数字在排序数组中出现的次数
剑指offer 55. 数字在排序数组中出现的次数
110 0
求整数序列中出现次数最多的数
求整数序列中出现次数最多的数
187 0
13.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
100 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等