首页 > 试题广场 >

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

[编程题]数字在升序数组中出现的次数
  • 热度指数:604575 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的非降序数组和一个非负数整数 k ,要求统计 k 在数组中出现的次数

数据范围:,数组中每个元素的值满足 
要求:空间复杂度 ,时间复杂度
示例1

输入

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

输出

4
示例2

输入

[1,3,4,5],6

输出

0
二分查找,参考剑指Offer,但是用的非递归。

public class Solution {
    	public  int GetNumberOfK(int[] array,int k){
		if(array==null||array.length==0)
			return 0;
		int first=getFirstK(array,k,0,array.length-1);
		int last=getLastK(array,k,0,array.length-1);
		if(first==-1 ||last==-1){
			return 0;
		}
		else{
			return last-first+1;
		}
		
	}
	
	public  int getFirstK(int[] array,int k,int start,int end){
		while(start<=end){
			int mid=(start+end)/2;
			if(k<array[mid])
				end=mid-1;
			else if(k>array[mid])
				start=mid+1;
			else{
				if((mid>0&&array[mid-1]!=k)||mid==0)
					return mid;
				else{
					end=mid-1;
				}
			}
		}
		return -1;
	}
	
	public  int getLastK(int[] array,int k ,int start,int end){
		while(start<=end){
			int mid=(start+end)/2;
			if(k<array[mid])
				end=mid-1;
			else if(k>array[mid])
				start=mid+1;
			else{
				if((mid<array.length-1&&array[mid+1]!=k)||mid==array.length-1)
					return mid;
				else{
					start=mid+1;
				}
			}
		}
		return -1;
	}
}

发表于 2016-07-17 11:41:39 回复(4)
Ron头像 Ron
/*二分查找,分治递归
*/
public class Solution {
    public  int GetNumberOfK(int [] array , int k) {
    	int length = array.length;
    	if(length <=0 || array == null){
    		return 0;
    	}
    	int num = array[length/2];
    	int[] arrayLeft;
    	int[] arrayRight;
    	int count = 0;
    	if(num > k){
    		arrayLeft = Arrays.copyOfRange(array, 0, length/2);
    		count = GetNumberOfK(arrayLeft, k);
    	}
    	if(num < k){
    		arrayRight = Arrays.copyOfRange(array, length/2+1, length);
    		count = GetNumberOfK(arrayRight, k);
    	}
    	if(num == k){
    		count++;
    		int leftCount = 0;
    		int rightCount = 0;
    		int leftNum;
    		int rightNum;
    		for(int i = 1; i <= length/2; i++){
    			leftNum = array[length/2-i];
    			if(leftNum==k){
    				leftCount++;
    			}else{ 				
    				break;
    			}
    		}
    		count += leftCount;
    		for(int i = 1; i <= length/2-1;i++){
    			rightNum = array[length/2+i];
    			if(rightNum==k){
    				rightCount++;
    			}else{
    				break;				
    			}
    		}
			count += rightCount;
    	}
    	return count;
    }
}

发表于 2015-07-05 16:28:41 回复(3)
class Solution {
private:
    int binaryFind(vector<int> &data, int begin, int end ,int k){
		int ind = -1;
		if(begin >= end) return -1;
		int mid = (end + begin) / 2;
		if(k == data[mid]) return mid;
		if((ind = binaryFind(data,begin,mid,k)) != -1) return ind;
		if((ind = binaryFind(data,mid+1,end,k)) != -1) return ind;
		return -1;
    }
    
public:
    int GetNumberOfK(vector<int> data ,int k) {
			int ind = binaryFind(data,0,data.size(),k);
			if(ind == -1) return 0;
			int pos = ind;
			int cnt = 1;
			while(--pos >= 0 && k == data[pos]) ++cnt;
			while(++ind < data.size() && k == data[ind]) ++cnt;
			return cnt;
    }
    
    
};

发表于 2015-09-06 11:58:31 回复(4)
该题如果用python来解的话方法可以使用python提供的函数直接求得
也可以避开库函数,使用自己的方法来解
class Solution:
    # 二分法找到k值的位置
    def BinarySearch(self, data, mlen, k):
        start = 0
        end = mlen - 1
        while start <= end:
            mid = (start + end) / 2
            if data[mid] < k:
                start = mid + 1
            elif data[mid] > k:
                end = mid - 1
            else:
                return mid
        return -1

    def GetNumberOfK(self, data, k):
        # write code here
        mlen = len(data)
        # 先使用二分法找到k值的位置
        index = self.BinarySearch(data, mlen, k)
        if index == -1:
            return 0
        # 分别向该位置的左右找
        count = 1
        for i in range(1,mlen):
            if index + i < mlen and data[index+i] == k:
                count += 1
            if index - i >= 0 and data[index-i] == k:
                count += 1
        return count

发表于 2018-05-06 09:43:32 回复(3)

int GetNumberOfK(vector<int>& A, int target) {
    if (A.empty()) return 0;

    auto it_lb = std::lower_bound(A.begin(), A.end(), target);
    auto it_ub = std::upper_bound(A.begin(), A.end(), target);

    return (it_ub - it_lb);
}

编辑于 2017-07-30 22:35:12 回复(2)
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array.length==0) return 0;
        int low = 0;
        int high = array.length-1;
        int mid = (low+high)/2;
        int count = 0;
        while(low<=high){
            mid = (low+high)/2;
            if(array[mid]>k){
                high = mid-1;
            }else if(array[mid]<k){
                low = mid+1;
            }else{    
                count = 1;
                int temp = mid-1;
                while(temp>=0 && array[temp]==array[mid]){
                    count++;
                    temp--;
                }
                temp = mid+1;
                while(temp<array.length && array[temp]==array[mid]){
                    count++;
                    temp++;
                }
                break;
            }
        }
        return count;
    }
}

发表于 2015-04-12 19:16:03 回复(0)
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto left = lower_bound(data.begin(), data.end(), k);
        auto right = upper_bound(data.begin(), data.end(), k);
        return right - left;
    }
};

发表于 2017-10-28 00:17:22 回复(0)
/* 先用二分查找找出某个k出现的位置,然后再分别向前和向后查找总的个数*/
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int i = binaryFind(data,0,data.size(),k);
        if( i == -1) return 0;
        int sum = 1;
        for(int j = i - 1; j >= 0; j--){
            if(data[j] == k) sum++;
            else break;
        }
        for(int j = i + 1; j < data.size(); j++){
            if(data[j] == k) sum++;
            else break;
        }
        return sum;
    }
    
    int binaryFind(vector<int> &data, int begin, int end ,int k){
        if(begin >= end) return -1;
        int mid = (begin + end) / 2;
        if(data[mid] == k) return mid;
        int res = -1;
        if((res = binaryFind(data,begin,mid,k)) != -1) return res;
        if((res = binaryFind(data,mid + 1, end,k) != -1)) return res;
        return -1;
    }
};

发表于 2015-08-17 17:00:39 回复(8)
//因为data中都是整数,所以可以稍微变一下,不是搜索k的两个位置,而是搜索k-0.5和k+0.5
//这两个数应该插入的位置,然后相减即可。
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
    }
private:
    int biSearch(const vector<int> & data, double num){
        int s = 0, e = data.size()-1;      
        while(s <= e){
            int mid = (e - s)/2 + s;
            if(data[mid] < num)
                s = mid + 1;
            else if(data[mid] > num)
                e = mid - 1;
        }
        return s;
    }
};

编辑于 2017-06-05 14:45:53 回复(92)
public int GetNumberOfK(int[] array , int k) {
    if(array == null || array.length == 0) return 0;
    int l = 0, r = array.length-1;
    int count = 0;
    while(l <= r){
        int mid = (l+r) >> 1;
        if(array[mid] < k){
            l = mid + 1;
        }else if(array[mid] > k){
            r = mid - 1;
        }else{
            count++;
            l = mid-1;
            r = mid+1;
            while(l >= 0 && array[l] == k){
                count++;
                l--;
            }
            while(r < array.length && array[r] == k){
                count++;
                r++;
            }
            break;
        }
    }
    return count;
}

发表于 2021-10-07 22:00:56 回复(0)
# -*- coding:utf-8 -*-
# 时间复杂度O(logn),我的方法不用找最前和最后的k,是递归中直接计算k的个数
class Solution:
    def GetNumberOfK(self, data, k):
        if not data:
            return 0
        return self.helper(data,k)

    def helper(self,data,k):
        if not data:
            return 0
        left, right = 0, len(data) - 1
        mid = (left + right) // 2
        if data[mid] > k:
            return self.helper(data[:mid], k)
        elif data[mid] < k:
            return self.helper(data[mid + 1:], k)
        else:
            return 1 + self.helper(data[:mid], k) + self.helper(data[mid + 1:], k)

发表于 2019-07-18 12:44:32 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data or not k:
            return 0
        
        frist = self.getFrist(data,k)
        last = self.getLast(data, k)
        
        if frist > -1 and last > -1:
            return last - frist + 1
        return 0
        # 二分查找数组中k的第一位
    def getFrist(self, data, k):
        begin = 0
        end = len(data) - 1
        mid = int((begin + end)/2)
        while begin <= end:
            if data[mid] < k:
                begin = mid + 1
            elif data[mid] > k:
                end = mid - 1
            else:
                if mid <= begin or data[mid-1] != k:
                    return mid
                else:
                    end = mid - 1
            mid = int((begin + end)/2)
        return -1
    # 二分查找数组中k的最后一位
    def getLast(self, data, k):
        begin = 0
        end = len(data) - 1
        mid = int((begin + end)/2)
        while begin <= end:
            if data[mid] < k:
                begin = mid + 1
            elif data[mid] > k:
                end = mid - 1
            else:
                if mid >= end or data[mid+1] != k:
                    return mid
                else:
                    begin = mid + 1
            mid = int((begin + end)/2)
        return -1
发表于 2018-04-20 22:52:46 回复(0)
java对这种题就是简单,用map
import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       Map<Integer, Integer> map = new HashMap<Integer, Integer>();
       for(int i=0;i<array.length;i++){
           if(!map.containsKey(array[i])){
       map.put(array[i], 1);
      }else{
       map.put(array[i], map.get(array[i])+1);
      }
       }
        return map.get(k)==null?0:map.get(k);
    }
}

发表于 2017-03-27 15:58:32 回复(2)

思路

  • 扫描数组思路很简单,时间复杂度为O(N),这里采用二分搜索获得logn的时间复杂度。
  • 由于数组已经有序,因此只需找到开头的k和结尾的k即可。

伪代码1:找到开头的k

  1. 一旦发现start>end,就说明数组中根本没有K,所以返回-1表示出错;
  2. 计算中点位置,将中点的值和k进行比较: 2.1. 若k小于中点值,则在前半段找 2.2. 若k大于中点值,则在后半段找 2.3. 若k等于中点值:
     a)若中点已经是数组第一个元素,则直接返回中点位置;
     b)若中点值的前一个元素和中点值不同,则直接返回中点位置;
     c)若中点值前一个元素和中点值相同,则继续在前半段找;
    
  3. 计算出新的start、end后继续递归。

伪代码2:主函数

  1. 健壮性判断:若数组为空、数组的第一个元素大于k、最后一个元素小于k,则根本不存在k,直接返回0.
  2. 分别计算k开头位置、结尾位置
  3. 只要其中一个为-1则返回-1;否则返回(结尾-开头+1)
public int GetNumberOfK(int [] array , int k) {

    // 若序列最小值大于k、最大值小于k,则k不存在!
    if ( array==null || array.length<=0 || k < array[0] || k > array[array.length-1] ) return 0;

    int firstK = GetFirstK( array, 0, array.length-1, k );
    int lastK = GetLastK( array, 0, array.length-1, k );

    if ( firstK==-1 || lastK==-1 ) return -1;

    return (lastK-firstK)+1;
}

private int GetFirstK( int[] array, int start, int end, int k ) {
    if ( start > end ) return -1; 

    int mid = ( start+end ) >> 1;
    if ( k < array[mid] ){
        end = mid-1;
    }
    else if ( k > array[mid] ){
        start = mid + 1;
    }
    else {
        if ( mid==0 || array[mid-1]!=array[mid] ) {
            return mid;
        }
        else {
            end = mid-1;
        }
    }

    return GetFirstK( array, start, end, k );
}

private int GetLastK( int[] array, int start, int end, int k ) {
    if ( start > end ) return -1; 

    int mid = ( start+end ) >> 1;
    if ( k < array[mid] ){
        end = mid-1;
    }
    else if ( k > array[mid] ){
        start = mid + 1;
    }
    else {
        if ( mid==array.length-1 || array[mid+1]!=array[mid] ) {
            return mid;
        }
        else {
            end = mid+1;
        }
    }

    return GetLastK( array, start, end, k );
}
发表于 2017-03-22 11:26:03 回复(0)
/*写了一大堆就是库函数一句话*/
class Solution {
public:
    int GetFirstK(vector<int>data,int k,int start,int end)
    {
        if(start>end)
            return -1;
        int middleIndex = (start+end)/2;
        int middleData = data[middleIndex];
        if(middleData==k)
        {
            if((data[middleIndex-1]!=k&&middleIndex>0)||middleIndex==0)
                return middleIndex;
            else
                end = middleIndex-1;
         }
        else if(data[middleIndex]>k)
            end = middleIndex-1;
        else
            start = middleIndex+1;
        
        return GetFirstK(data,k,start,end);
    }
    int GetLastK(vector<int>data,int k,int start,int end)
    {
        if(start>end)
            return -1;
        int middleIndex = (start+end)/2;
        int middleData = data[middleIndex];
        if(middleData==k)
        {
            if((data[middleIndex+1]!=k&&middleIndex>0)||middleIndex==0)
                return middleIndex;
            else
                start = middleIndex+1;
         }
        else if(data[middleIndex]>k)
            end = middleIndex-1;
        else
            start = middleIndex+1;
        
        return GetLastK(data,k,start,end);
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int length = data.size();
        if(length<=0)
            return 0;
        int start = 0;
        int end = length-1;
        int firstNumber = GetFirstK(data,k,start,end);
        int lastNumber = GetLastK(data,k,start,end);
        if(firstNumber==-1||lastNumber==-1)
            return 0;
        else
        return lastNumber-firstNumber+1;
    }
};

发表于 2016-03-24 16:05:03 回复(0)
 //使用STL算法count 循序查找O(n)
    int GetNumberOfK(vector<int> data, int k) {
        return count(data.begin(), data.end(), k);
    }
 //利用STL的multimap容器底层以红黑树为基础,构造成本O(n),查询成本O(log n)
    int GetNumberOfK(vector<int> data, int k) {
        multiset<int> msData(data.begin(), data.end());
        return msData.count(k);
    }
    //利用STL库函数lower_bound()和upperBound(),O(log n)
    int GetNumberOfK(vector<int> data ,int k) {
        auto iter1 = lower_bound(data.begin(), data.end(), k);
        auto iter2 = upper_bound(data.begin(), data.end(), k);
        return static_cast<int>(iter2 - iter1);
    }

编辑于 2018-04-26 11:12:17 回复(0)
public int GetNumberOfK(int[] array, int k) {
        int l, r, m, l1, r1;
        for (l = 0, r = array.length - 1, m = (l + r) >> 1; l < m; m = (l + r) >> 1)
            if (k <= array[m])
                r = m;
            else
                l = m + 1;
        for (l1 = 0, r1 = array.length - 1, m = (l1 + r1) >> 1; l1 < m; m = (l1 + r1) >> 1) 
            if (k < array[m])
                r1 = m - 1;
            else
                l1 = m;

        return r > -1 && array[l] == k ? r1 - l + 1 : 0;
    }

用递归:
public int GetNumberOfK(int[] array, int k) {
		if (array == null || array.length == 0)
			return 0;
		
		int t = getFirst(array, 0, array.length - 1, k);
		if (t != -1)
			return getLast(array, 0, array.length - 1, k) - t + 1;
		
		return 0;
	}

	int getFirst(int[] array, int s, int e, int k) {
		if (s >= e)
			return array[s] == k ? s : -1;
		
		int m = (s + e) / 2;
		if (array[m] < k)
			return getFirst(array, m + 1, e, k);
		else
			return getFirst(array, s, m, k);
	}

	int getLast(int[] array, int s, int e, int k) {
		if (s >= e) {
			if (array[s] == k)
				return s;
			return array[s - 1] == k ? s - 1 : -1;
		}
		
		int m = (s + e) / 2;
		if (array[m] <= k)
			return getLast(array, m + 1, e, k);
		else
			return getLast(array, s, m, k);
	}

编辑于 2020-09-23 11:48:12 回复(3)
class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        return data.count(k)

发表于 2022-07-28 22:54:00 回复(0)
    
//这题就用二分先找到一个,再判断前面和后面的数是不是也为目标值就行了
int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()==0)
            return 0;
        int l =0,n=data.size()-1;
        while(l<=n)
        {
            int mid = (l+n)/2;
            if(data[mid]==k)
            {
                int count =0;
                int m=mid;
                while(mid>=0&&data[mid]==k)//判断前一个是否为目标值(注意防止数组越界)                  {
                    count+=1;
                    mid--;
                }
                
                while(m+1<=n&&data[m+1]==k)//判断后一个是否为目标值(注意防止数组越界)
                {
                    count++;
                    m++;
                }
                return count;
            }
            if(data[mid]>k)
            {
                n=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return 0;
    }

发表于 2022-03-11 22:54:11 回复(0)
int find(int*data,int len,int k,int flag)
{
    int left=0,right=len-1,mid;
    while(left<=right){
        mid=left+(right-left)/2;
        if(data[mid]>k)
            right=mid-1;
        else if(data[mid]<k)
            left=mid+1;
        else{
            if(flag==0){//flag==0,找最左边数字,
                if(mid==left ||data[mid-1]!=k) return mid;
                else right=mid-1;//把中心向左推
            }else {
                if(mid==right||data[mid+1]!=k) return mid;
         else left=mid+1;
            }
        }
    }
    return -1;
}

int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    if(dataLen==0) return 0;
    int left=find(data,dataLen,k,0);
    int right=find(data,dataLen,k,1);
    if(left==-1&&right==-1) return 0;//没找到
    return right-left+1;
}

发表于 2022-02-17 10:57:59 回复(0)