首页 > 试题广场 >

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

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

热度指数：610855 时间限制：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 3

吉吉锅锅

貌似递归更复杂，更难想一点吧

发表于 2022-09-05 09:16:00 回复(0)

Python 3

牛客806311391号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param data int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
def GetNumberOfK(self , data: List[int], k: int) -> int:
# write code here
# return data.count(k)
return len([i for i in data if i==k])

发表于 2022-08-14 19:31:48 回复(0)

Python 3

牛客913332660号

#利用位运算来做，异或操作，相同为0，不同为1

class Solution:

def GetNumberOfK(self , data: List[int], k: int) -> int:
# write code here
cnt = 0
for num in data:
if num^k==0:
cnt+=1
return cnt

发表于 2022-08-11 17:14:21 回复(0)

Python 3

来个offer叭！

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        return data.count(k)

发表于 2022-07-28 22:54:00 回复(0)

Python 3

Vivimore

class Solution:
    # 二分查找
    def bi_search(self , data: List[int], k: int) -> int:
        left = 0
        right = len(data) - 1
        while left <= right:
            mid = (left + right) // 2
            if data[mid] < k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
        return left

    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # 查找k+0.5 和 k-0.5应该出现的位置
        return self.bi_search(data, k + 0.5) - self.bi_search(data, k-0.5)

发表于 2022-05-09 20:02:27 回复(0)

Python 3

一只兔子的奇幻之旅

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        id=self.indexof(data, k)
        if id==-1:
            return 0
        else:
            return self.find(data,id,k)
    def indexof(self,data,val):
        low=0
        high=len(data)-1
        while low<=high:
            mid=low+((high-low)>>1)
            if data[mid]>val:
                high=mid-1
            elif data[mid]<val:
                low=mid+1
            else:
                return mid
        return -1
    def find(self,arr,p,val):
        x=[]
        f=p
        while f>=0 and arr[f]==val:
            f-=1
        x.append(f+1)
        while  p<len(arr) and arr[p]==val:
            p+=1
        x.append(p)
        return x[1]-x[0]

发表于 2022-04-05 09:21:24 回复(0)

Python 3

kinter1

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        if not data:
            return 0
        if data[0] > k:
            return 0
        if data[0] == k:
            count = 0
            for i in range(len(data)):
                if data[i] != k:
                    break
                count += 1
            return count
        if data[0] < k:
            mid = len(data) // 2
            if mid > 0:
                return self.GetNumberOfK(data[:mid], k) + self.GetNumberOfK(data[mid:], k)
            else:
                return 0

二分递归

发表于 2022-03-09 21:16:09 回复(0)

Python 3

Herschel555

二分法查找，找到后再左右分别查找相同k的个数

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # write code here
        left = 0
        right = len(data) - 1
        num = 0
        while (left<=right):
            mid = left + int((right - left) / 2)
            if data[mid] == k:
                num += 1
                break
            elif data[mid] < k:
                left = mid + 1
            else:
                right = mid - 1
        if num==0:
            return 0
        else:
            fleft = mid - 1
            fright = mid + 1
            while fleft>=0 and (data[fleft]==k):
                num += 1
                fleft -= 1
            while fright<=(len(data)-1) and (data[fright]==k):
                num += 1
                fright += 1
            return num

发表于 2022-01-23 23:40:07 回复(0)

Python 3

丿52赫兹丿

from collections import Counter
class Solution:
def GetNumberOfK(self , data: List[int], k: int) -> int:
# write code here
if k in data:
dic = dict(Counter(data))
if len(dic) > 0:
return dic[k]
return 0

发表于 2022-01-23 09:23:15 回复(0)

Python 3

Joy_9

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # write code hereta
        i=0
        j=len(data)-1
        if j==0:
            return 1 if data[0]==k else 0
        if not data:
            return 0
        while i<=j:
            mid=(i+j)//2
            if data[mid]<k:
                i=mid+1
            elif data[mid]>=k:
                j=mid-1
        lower=j
        i=0
        j=len(data)-1
        while i<=j:
            mid=(i+j)//2
            if data[mid]<=k:
                i=mid+1
            elif data[mid]>k:
                j=mid-1
        return i-lower-1 if i-lower-1>0 else 0

发表于 2022-01-06 08:48:46 回复(0)

Python 3

Lenn0x

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # write code here
        if len(data)==0:return 0
        n=len(data)
        left,right=0,n-1
        while left<=right:
            mid=(left+right)//2
            if data[mid]<k:
                left=mid+1
            else:
                right=mid-1
            l=right
        left,right=0,n-1
        while left<=right:
            mid=(left+right)//2
            if data[mid]<=k:
                left=mid+1
            else:
                right=mid-1
        r=left
        cur=r-l-1
        return cur

发表于 2022-01-01 18:24:21 回复(0)

Python 3

Hudas.

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        new_data = set(data)
        if k not in new_data:
            return 0
        return(data.count(k))

发表于 2021-12-28 17:57:55 回复(0)

Python 3

行舟201908241343644

class Solution:
result = 0
def GetNumberOfK(self , data: List[int], k: int) -> int:
m = int(len(data)/2)
if (m == 0) & (len(data) == 0):
return self.result
elif data[m] == k:
self.result += 1
return self.GetNumberOfK(data[:m]+data[m+1:],k)
elif data[m] < k:
return self.GetNumberOfK(data[m+1:],k)
else:
return self.GetNumberOfK(data[:m],k)

发表于 2021-12-14 16:18:34 回复(0)

Python 3

ZzBobobo

class Solution:
    def GetNumberOfK(self, data, k):
        return data.count(k)

发表于 2021-12-03 18:03:57 回复(0)

Python 3

Key丶LW

#用二分法查找

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # write code here
        def find(arr,k):
            l = 0
            r = len(arr)
            while l<r:
                mid = int((l+r)/2)
                if arr[mid] < k:
                    l = mid + 1
                else:
                    r = mid
            return l
        
        first = find(data, k)
        last = find(data, k+1)
        print(first)
        print(last)
        return last - first

发表于 2021-11-14 14:23:03 回复(0)

Python 3

JSFaner

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        start = 0
        left,right=0,len(data)-1
        while left<=right:
            mid = (left+right)//2
            if data[mid] < k: left=mid +1
            elif data[mid] > k: right=mid -1
            elif data[mid] == k: right=mid -1
        if left >= len(data)&nbs***bsp;data[left] != k:
            return 0
        start = left
        left,right=0,len(data)-1
        while left<=right:
            mid = (left+right)//2
            if data[mid] < k: left=mid +1
            elif data[mid] > k: right=mid -1
            elif data[mid] == k: left=mid +1
        if right > -1 and data[right] == k:
            return right - start + 1

发表于 2021-11-13 20:03:29 回复(0)

Python 3

长歌行abc

def binary_search(alist, item):
    low = 0  high = len(alist) - 1  while low <= high:
        mid = (low + high) // 2  if alist[mid] == item: return mid elif alist[mid] > item:
            high = mid - 1  else:
            low = mid + 1  return None count=0 w=input()
s=int(w[-1])
w=w[1:-3] if len(w)==0: print("0") else:
    w=list(map(int,w.split(",")))
    num=binary_search(w,s) if num==None: print("0") else: if w[0]==s: while w[num]>=s and num!=0:
                num-=1  a=num else: while w[num]>=s:
                num-=1  a=num+1  if w[len(w)-1]==s: while w[a]==s and a!=len(w)-1:
                count+=1  a+=1  print(count+1) else: while w[a]==s:
                count+=1  a+=1  print(count)