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

题目描述:

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

输入:

每个测试案例包括两行:

第一行有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),最坏情况下为O(n),剑指offer上给的思路是两次用二分查找分别找到该数字第一次和最后一次出现的位置,这样的时间复杂度平均和最坏都是O(logn),稍好些》

下面贴上我按照自己思路写的代码:

#include<stdio.h>
#include<stdlib.h>  

/*
二分查找法计算key出现的次数
本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
*/
int CountTimesInArrays(int *arr,int len,int key)
{
    if(arr==NULL || len<1)
        return 0;  

    int start = 0;
    int end = len-1;
    int mid;
    while(start <= end)
    {
        mid = (start+end)>>1;
        if(arr[mid] == key)
            break;
        else if(arr[mid] > key)
            end = mid-1;
        else
            start = mid+1;
    }  

    //包含了出现0次的情况
    int times = 0;
    if(start <= end)
    {
        int i;
        times = 1;
        for(i=mid+1;i<=end;i++)
            if(arr[i] == key)
                times++;
        for(i=mid-1;i>=start;i--)
            if(arr[i] == key)
                times++;
    }
    return times;
}   

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        int *arr = (int *)malloc(n*sizeof(int));
        if(arr == NULL)
            exit(EXIT_FAILURE);  

        int i;
        for(i=0;i<n;i++)
            scanf("%d",arr+i);
        int m;
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            int k;
            scanf("%d",&k);
            printf("%d\n",CountTimesInArrays(arr,n,k));
        }  

        free(arr);
        arr = NULL;
    }
    return 0;
}

作者:csdn博客 兰亭风雨

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索数组
, 排序
, 数字
, 整数
, 次数
一行
java数组数字出现次数、excel按出现次数排序、excel 出现次数排序、按出现次数排序、易语言数组中出现次数,以便于您获取更多的相关知识。

时间: 2016-10-30

求数字在排序数组中出现的次数的相关文章

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

题目: 统计一个数字在排序数组中出现的次数. 通过折半查找, 找到首次出现的位置, 再找到末次出现的位置, 相减即可. 时间复杂度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,如果不是那么该中间位置就

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

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

【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> #in

[经典面试题]排序数组中绝对值最小元素

[题目] 题目为: 有一个已经排序的数组(升序),数组中可能有正数.负数或0,求数组中元素的绝对值最小的数,要求,不能用顺序比较的方法(复杂度需要小于O(n)),可以使用任何语言实现 例如,数组{-20,-13,-4, 6, 77,200} ,绝对值最小的是-4. [分析] 给定数组是已经排好序的,且是升序,没有重复元素. 一个简单的思路,就是一次性遍历数组,求出数组的元素的绝对值的最小值,这样的时间复杂度为O(n). 但是,这样就浪费了题目的一个条件:数组是已经排好序的.所以,需要对原来的题目

java-JAVA排序问题求若干个数的数组中第k个最大值

问题描述 JAVA排序问题求若干个数的数组中第k个最大值 代码: import java.util.Scanner; public class Sorting0{ public int[] sort(int[] num){ for(int i=0;i<num.length;i++){ for(int j=0;j<num.length-i-1;j++){ if(num[j]<num[j+1]){ int n=0; n=num[j]; num[j]=num[j+1]; num[j+1]=n;

visual studio 2010-如何用数组储存依次一串数的每个数字,如何数组中计数数字数

问题描述 如何用数组储存依次一串数的每个数字,如何数组中计数数字数 比如输入1010,怎么做让数组自动储存其中每个数,数组的数据类型应该是什么,然后如何统计数组里已经输了四个数?新手,谢谢. 解决方案 不用数组就可以了,我是用java的程序员,java中String,接收后,有自己的length属性,表示这个字符串有几个字符 解决方案二: 不用数组就可以了,我是用java的程序员,java中String,接收后,有自己的length属性,表示这个字符串有几个字符 解决方案三: #include

java去除已排序数组中的重复元素_java

题目描述 给定一个已排序的数组,去除数组中的重复元素,只保留一个重复的元素,并且返回新的数组长度. 要求: 不要给数组分配额外的空间,你必须使用常量的内存大小进行原地操作. 例如: 给出数组A=[1,1,2],你的函数调用之后必须返回长度length=2,并且A现在变成[1,2]. 输入 一个已排序的数组,例如[1,1,2]. 输出 返回数组新的长度,例如length=2. 快慢指针法 设置fast指针遍历数组,slow指针指向不重复元素的下一位. public static int remov

ruby 怎么利用正则表达式在把一个字符串数组中的数字放到一个数组中?

问题描述 ruby 怎么利用正则表达式在把一个字符串数组中的数字放到一个数组中?str='100good200bad300ok'问题补充:说错了是把一个字符串中的所有数字放到一个数组中:)问题补充:是 100 200 300不过还是谢谢sunfjun 解决方案 str='100good200bad300ok' str.scan(/d+/)解决方案二:String的这个scan方法真不错, shaquan6776解决方案三:'100good200bad300ok'.split(/[^d]/).re