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

题目:统计一个数字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;
}
时间: 2024-09-21 14:14:23

【1】数字在数组中出现的次数的相关文章

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

题目描述: 统计一个数字在排序数组中出现的次数. 输入: 每个测试案例包括两行: 第一行有1个整数n,表示数组的大小.1<=n <= 10^6. 第二行有n个整数,表示数组元素,每个元素均为int. 第三行有1个整数m,表示接下来有m次查询.1<=m<=10^3. 下面有m行,每行有一个整数k,表示要查询的数. 输出: 对应每个测试案例,有m行输出,每行1整数,表示数组中该数字出现的次数. 样例输入: 8 1 2 3 3 3 3 4 5 1 3 样例输出: 4 我做这道题,是先用二

如何求数字在排序数组中出现的次数

题目: 统计一个数字在排序数组中出现的次数. 通过折半查找, 找到首次出现的位置, 再找到末次出现的位置, 相减即可. 时间复杂度O(logn). 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <stdlib.h> #include <string.h> int GetFirstK

剑指offer系列之三十六:数字在排序数组中出现的次数

题目描述 统计一个数字在排序数组中出现的次数. 因为是排序数组,自然联想到二分查找算法,这样我们在二分的时候可能会获取多个相同的数字.就是说,中间那个位置的值可能刚好是统计的那个值,假设为k.那么k还有可能在前面或者后面出现,在这个基础上继续二分当然也是可以的,如果能够在使用二分查找算法的时候统计出第一个k和最后一个k出现的位置,那么k出现的次数自然就确定了.第一个k出现的位置,可以使用二分查找算法,如果中间位置的值刚好是k,那么继续比较中间位置前面位置的值是不是也是k,如果不是那么该中间位置就

基于Java代码实现数字在数组中出现次数超过一半_java

下文通过几种方法给大家介绍java数组数字出现次数,具体内容如下所示: 方法一: 数组排序,然后中间值肯定是要查找的值. 排序最小的时间复杂度(快速排序)O(NlogN),加上遍历. 方法二: 使用散列表的方式,也就是统计每个数组出现的次数,输出出现次数大于数组长度的数字. 方法三: 出现的次数超过数组长度的一半,表明这个数字出现的次数比其他数出现的次数的总和还多. 考虑每次删除两个不同的数,那么在剩下的数中,出现的次数仍然超过总数的一般,不断重复该过程,排除掉其他的数,最终找到那个出现次数超过

《剑指offer》-数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数. 首先吐槽下出题人的用词,啥叫排序数组?"排序"是个动词好么,"有序"作为一个形容词表示状态,修饰"数组",才是合适的. 题目考察二分查找,首先找到指定数字最先出现的位置,然后找到最后出现的位置,他们的距离+1就是个数. class Solution14{ public: int GetNumberOfK(vector<int> data, int k){ if (data.empty()){ re

c语言-C语言插入一个数字到数组中,然后排序 麻烦各位解答一下 看代码

问题描述 C语言插入一个数字到数组中,然后排序 麻烦各位解答一下 看代码 int i,j,temp; int count[9]; printf("请输入数值:n"); for(i=1;i<=8;i++) { printf("count[%d]=",i); scanf("%d",&count[i]); } for(i=1;i<=8;i++) { for(j=i+1;j<=8;j++) { if(count[j]>co

如何读取txt中的数字到数组中,txt文件中的内容如下

问题描述 9.02725E-56.16796E71.09923E-41023378.99146E-55.1843E68.97233E-5-38108.38.98244E-54.65385E68.98291E-52.82616E61.00324E-4-42622.28.97477E-5-69155.5每一行的两个数之间是"tab"键,行于行之间是"enter"键需要将每列数字分别读到两个数组中 解决方案 解决方案二:FileStremfs=newFileStream(

php数组函数序列 之array_count_values() 统计数组中所有值出现的次数函数_php技巧

array_count_values()定义和用法 array_count_values() 函数用于统计数组中所有值出现的次数. 本函数返回一个数组,其元素的键名是原数组的值,键值是该值在原数组中出现的次数. 语法 array_count_values(array) 参数 描述 array 必需.规定输入的数组. 例子 复制代码 代码如下: <?php $a=array("Cat","Dog","Horse","Dog"

php计算数组相同值出现次数的代码(array_count_values)_php技巧

php计算数组相同值出现次数,可以使用php自带函数array_count_values : 说明 array array_count_values ( array $input )array_count_values() 返回一个数组,该数组用 input 数组中的值作为键名,该值在 input 数组中出现的次数作为值. array_count_values() 例子 复制代码 代码如下: <?php $array = array(1, "hello", 1, "wo