首页 > 试题广场 >

数字在升序数组中出现的次数

[编程题]数字在升序数组中出现的次数

热度指数：611671 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围： $0 \le n \le 1000 , 0 \le k \le 100$ ，数组中每个元素的值满足 $0 \le val \le 100$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

示例1

输入

[1,2,3,3,3,3,4,5],3

输出

示例2

输入

[1,3,4,5],6

输出

算法知识视频讲解

Python

牛客549486156号

# -*- coding:utf-8 -*-
import bisect
class Solution:
    def GetNumberOfK(self, data, k):
        return bisect.bisect_right(data,k) - bisect.bisect_left(data, k)

编辑于 2021-07-11 13:03:56 回复(0)

Python

王大涛

class Solution:
def GetNumberOfK(self, data, k):
# write code here
if k not in data:
return 0
return data.count(k)

发表于 2021-05-12 21:31:55 回复(0)

Python

猫牛

class Solution:
    def lower_bound(self, data, target):
        left, right = 0, len(data)-1
        while left <= right:
            mid = left + (right-left) // 2
            if data[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        return left
    
    def upper_bound(self, data, target):
        left, right = 0, len(data)-1
        while left <= right:
            mid = left + (right-left) // 2
            if data[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1

        return right
    
    def GetNumberOfK(self, data, k):
        # write code here
        first_idx = self.lower_bound(data, k)
        last_idx = self.upper_bound(data, k)

        return last_idx - first_idx+1

发表于 2021-04-17 19:43:35 回复(0)

Python

闭眼听风3

# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here

return data.count(k)

这样写面试官会挂我吗

发表于 2021-03-01 10:13:45 回复(0)

Python

LHC0512

Python 解法一

from collections import defaultdict

class Solution:
    def GetNumberOfK(self, data, k):
        map1 = defaultdict(int)
        for v in data:
            map1[v] += 1
        return map1[k]

Python 解法二

import bisect

class Solution:
    def GetNumberOfK(self, data, k):
        l = bisect.bisect(data, k - 0.5)
        r = bisect.bisect(data, k + 0.5)
        return r - l

发表于 2021-02-22 23:32:55 回复(1)

Python

在下小6

python解法：
解法一：count()函数

"""
思路1:count()函数,时间复杂度O(n)；
"""
class Solution:
    def GetNumberOfK(self, data, k):
        return data.count(k)

解法二：直接遍历；

"""
思路2:直接遍历,时间复杂度O(n)；
"""
class Solution:
    def GetNumberOfK(self, data, k):
        res = 0
        for num in data:
            if num == k:
                res += 1
        return res

解法三：双指针法；

"""
思路3:双指针法,时间复杂度O(n)；
"""
class Solution:
    def GetNumberOfK(self, data, k):
        i,j = 0,len(data)-1
        if len(data) == 1:
            if k == data[0]:
                return 1
            else:
                return 0
        while(i<j):
            if data[i] != k:
                i += 1
            if data[j] != k:
                j -= 1
            if data[i] == k & data[j] == k:
                return j-i+1
        return 0

解法四：二分法；

"""
思路4:二分法,先二分查找到目标元素，之后再统计个数，时间复杂度O(logn)；
"""
class Solution:
    def GetNumberOfK(self, data, k):
        low, high = 0, len(data)-1
        count = 0
        while low <= high:
            # 寻找目标元素
            mid = (high - low) // 2 + low
            # 找到目标元素，统计个数
            if data[mid] == k:
                count += 1
                left = mid - 1
                while left >= low and data[left] == k:
                    count += 1
                    left -= 1
                right = mid + 1
                while right <= high and data[right] == k:
                    count += 1
                    right += 1
                return count
            # 继续寻找目标元素
            elif data[mid] > k:
                high = mid - 1
            else:
                low = mid + 1
        return count

发表于 2021-02-18 16:38:12 回复(0)

Python

12313242

思路：

1.先计算数列中小于等于k的个数，设为a

2.逆转数列，然后求得大于等于k的个数，设为b

3.a+b-len(数列)就是所求长度

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        n_larger = 0
        n_smaller = 0
        n = 0
        while n<len(data) and data[n]<=k:
            n_larger += 1
            n += 1
        nn = 0
        data.reverse()
        while nn<len(data) and data[nn]>=k:
            n_smaller += 1
            nn += 1
        return(n_larger + n_smaller -len(data))

发表于 2020-10-28 16:59:09 回复(0)

Python

老和山小学生

让一让， python版的二分法，复杂度O(lgn)


# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        begin = self.searchBegin(data, k, 0, len(data))
        end = self.searchEnd(data, k, 0, len(data))
        if begin == -1 and end == -1:
            return 0
        return end-begin+1
    
    def searchBegin(self, data, target, l, r):
        if l >= r:
            return -1
        cut = (l+r)//2
        if data[cut] > target:
            return self.searchBegin(data, target, l, cut)
        elif data[cut] < target:
            return self.searchBegin(data, target, cut+1, r)
        else:
            if cut == 0 or data[cut-1] != target:
                return cut
            else:
                return self.searchBegin(data, target, l, cut)
    
    def searchEnd(self, data, target, l, r):
        if l >= r:
            return -1
        cut = (l+r)//2
        if data[cut] > target:
            return self.searchEnd(data, target, l, cut)
        elif data[cut] < target:
            return self.searchEnd(data, target, cut+1, r)
        else:
            if cut == len(data)-1&nbs***bsp;data[cut+1] != target:
                return cut
            else:
                return self.searchEnd(data, target, cut+1, r)

编辑于 2020-10-15 22:03:20 回复(0)

Python

苏堤牧

可行？

from collections import Counter

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return Counter(data)[k]

编辑于 2020-09-11 15:35:10 回复(0)

Python

有个

首先我的代码通过了, 但是我有一点疑惑, 详情请看我倒数第二行, 为什么要写成这样?

# -*- coding:utf-8 -*-

class Solution:
def GetNumberOfK(self, data, k):
# write code here
if k not in data:
return 0
lbound, rbound = 0, 0
left, right = 0, len(data) - 1
while left < right:
mid = left + (right - left)// 2
if data[mid] < k:
left = mid + 1
else:
right = mid
lbound = left
left, right = 0, len(data) - 1
while left < right:
mid = left + (right - left) // 2
if data[mid] <= k:
left = mid + 1
else:
# data[mid] > k
right = mid
rbound = right + 1 if right == len(data) - 1 else right

return rbound - lbound

发表于 2020-08-31 20:15:17 回复(0)

Python

求上岸岸岸岸！！！

class Solution:
def GetNumberOfK(self, data, k):
# write code here
return len([i for i in data if i == k])

发表于 2020-07-26 11:23:50 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        count = 0
        for i in data:
            if i == k:
                count +=1
        return count

这可能是我刷剑指offer遇到的最简单的一个题了哈哈哈：首先看清函数名中指定参数，有data和k，那么我可以认为data就是排序数组，k就是需要我判断出现次数的那个数。于是遍历data中的数，当i等于k时，就使count+1，累计出现，累计+1。

发表于 2020-07-25 21:10:23 回复(0)

Python

求求来一个offer吧

def GetNumberOfK(data, k):
    n=data.index(k)
    m=data[::-1].index(k)
    m=len(data)-m
    return m-n

发表于 2020-07-22 10:13:44 回复(0)

Python

WeiKii

class Solution:
    def GetNumberOfK(self, data, k):
        
        if not data:
            return 0
        
        idx = len(data)//2
        
        if data[idx] > k:
            return self.GetNumberOfK(data[:idx], k)
        elif data[idx] < k:
            return self.GetNumberOfK(data[idx+1:], k)
        else:
            return 1 + self.GetNumberOfK(data[:idx], k) + self.GetNumberOfK(data[idx+1:], k)

发表于 2020-07-07 22:26:18 回复(0)

Python

自律人偶

Python

二分查找，同时加入对重复元素的处理

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.count=0
        self.data=None

    def GetNumberOfK(self, data, k):
        # write code here
        #二分法查找该数字
        if not data:return 0
        self.data=data
        self.BinarySearch(k)
        return self.count

    def BinarySearch(self,k):
        start=0
        length=len(self.data)-1
        while start<=length:
            middle=(start+length)//2
            if k == self.data[middle]:
                self.count +=1
                self.repeat(middle,k)
                break
            if k < self.data[middle]:
                length=middle-1
            else:
                start=middle+1

    def repeat(self,middle,k):
        frontIndex=1
        behindIndex=1
        
        if middle-frontIndex>=0:
            while self.data[middle-frontIndex]==k:
                self.count +=1
                frontIndex+=1
                if middle-frontIndex<0:break
        if middle+behindIndex<len(self.data)-1:
            while self.data[middle+behindIndex]==k:
                self.count +=1
                behindIndex+=1
                if middle+behindIndex>len(self.data)-1:break

编辑于 2020-06-11 22:35:25 回复(0)

Python

黄沙遮天

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        dict1={}
        for i in data:
            if i not in dict1:
                dict1[i]=1
            else:
                dict1[i]+=1
        if k in dict1:
            return dict1[k]
        else:
            return 0

很简单使用字典就行了

发表于 2020-03-18 00:03:04 回复(0)

Python

但行好事-莫问前程

一次遍历通过

1. 用字典存储k

2. 遍历列表，如果数组元素 == k,则字典key == k 的value+1

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        (2024)# write code here
        dic = dict()
        dic[k] = 0
        for i in range(len(data)):
            if data[i] == k:
                dic[data[i]] += 1
        return dic[k]

发表于 2020-03-10 11:15:58 回复(0)

Python

牛客447097232号

# -*- coding:utf-8 -*-
"""
与二分法搜索类似，但边界费了点工夫
查找第一个
查找最后一个
"""
class Solution:
    def GetNumberOfK(self, data, k):
        first_index = self.get_first_index(data, 0, len(data) - 1, k)
        last_index = self.get_last_index(data, 0, len(data) - 1, k)
        if first_index == -1:
            return 0
        else:
            return last_index - first_index + 1

    def get_first_index(self,data, start, end, k):
        """
        mid 等于目标且前一个元素不为目标则返回mid
        前一个元素为目标则向前搜索
        mid 大于目标前搜索
        mid 小于目标向后搜索
        注意不存在目标的情况
        :param data: 
        :param start: 
        :param end: 
        :param k: 
        :return: 
        """
        if end < start:
            return -1
        mid = (start + end)//2
        if data[mid] == k:
            if mid - 1 < 0&nbs***bsp;data[mid-1] != data[mid]:
                return mid
            else:
                end = mid - 1
        elif k < data[mid]:
            end = mid - 1
        else:
            start = mid + 1
        return self.get_first_index(data, start, end, k)

    def get_last_index(self,data, start, end, k):
        if end < start:
            return -1
        mid = (start + end)//2
        if data[mid] == k:
            if mid + 1 >= len(data)&nbs***bsp;data[mid+1] != data[mid]:
                return mid
            else:
                start = mid + 1
        elif k < data[mid]:
            end = mid - 1
        else:
            start = mid + 1
        return self.get_last_index(data, start, end, k)


s = Solution()
a = [3,3,3,3,4,5]
ans = s.GetNumberOfK(a,2)
print(ans)

发表于 2020-03-03 10:11:02 回复(0)

Python

天山剑客

# -*- coding:utf-8 -*-
# 解题思路：二分查找加左右遍历，数字出现的次数默认为0
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data:
            return 0

        if k < data[0]&nbs***bsp;k > data[-1]:
            return 0

        n = len(data)
        lowp = 0
        highp = n - 1
        flag = 0

        while lowp <= highp:
            mid = (lowp + highp) // 2
            if data[mid] < k:
                lowp = mid + 1
                continue

            if data[mid] > k:
                highp = mid - 1
                continue

            if data[mid] == k:
                flag = mid
                break

        i = flag
        j = flag + 1
        count = 0

        while i >= 0 and data[i] == k:
            count += 1
            i -= 1

        while j < n and data[j] == k:
            count += 1
            j += 1

        return count

发表于 2019-12-07 17:33:39 回复(0)

Python

Kirto先森

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        #优化, 查找左右边界也用二分查找 O(nlogn)
        #左中位数
        def bf_left(left, right):
            while left < right:
                mid = (left+right) >> 1
                if data[mid]<k:
                    left = mid+1
                else:
                    right = mid
            return left
        
        #右中位数
        def bf_right(left, right):
            while left < right:
                mid = (left+right+1) >> 1
                if data[mid]<=k:
                    left = mid
                else:
                    right = mid-1
            #防止left>right, 返回较小一个
            return right
        
        if not data:
            return 0
        n = len(data)
        left, right = 0, n-1
        mid = bf_left(left,right)
        if data[mid]!=k:
            return 0
        left = bf_left(left, mid-1)
        if data[left]!=k:
            left = mid
        right = bf_right(mid+1, right)
        if data[right]!=k:
            right = mid
        return right-left+1
        
        
        
        '''
        #方法：二分查找到该数字, 然后左右顺序查找边界, 平均时间复杂度O(n)
        if not data:
            return 0
        n = len(data)
        left, right = 0, n-1
        while left<right:
            mid = (left+right)>>1
            if mid<k:
                left = mid+1
            else:
                right = mid
        #左边
        count = 0
        if data[left]!=k:
            return 0
        
        while left>=0 and data[left]==k:
            count += 1
            left -= 1
        
        while right<n and data[right]==k:
            count += 1
            right += 1
        
        return count-1
        '''

发表于 2019-11-19 11:41:18 回复(0)