首页 > 试题广场 > 数字在排序数组中出现的次数
[编程题]数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
//因为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 回复(71)
看见有序,肯定就是二分查找了,算法比较简单,不多说,值得一提的是,不要拘泥于递归,要会循环写法。
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int length = array.length;
        if(length == 0){
            return 0;
        }
        int firstK = getFirstK(array, k, 0, length-1);
        int lastK = getLastK(array, k, 0, length-1);
        if(firstK != -1 && lastK != -1){
             return lastK - firstK + 1;
        }
        return 0;
    }
    //递归写法
    private int getFirstK(int [] array , int k, int start, int end){
        if(start > end){
            return -1;
        }
        int mid = (start + end) >> 1;
        if(array[mid] > k){
            return getFirstK(array, k, start, mid-1);
        }else if (array[mid] < k){
            return getFirstK(array, k, mid+1, end);
        }else if(mid-1 >=0 && array[mid-1] == k){
            return getFirstK(array, k, start, mid-1);
        }else{
            return mid;
        }
    }
    //循环写法
    private int getLastK(int [] array , int k, int start, int end){
        int length = array.length;
   		int mid = (start + end) >> 1;
        while(start <= end){
            if(array[mid] > k){
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else if(mid+1 < length && array[mid+1] == k){
                start = mid+1;
            }else{
                return mid;
            }
            mid = (start + end) >> 1;
        }
        return -1;
    }
}

发表于 2016-08-17 15:55:09 回复(47)
利用C++ stl的二分查找
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto resultPair = equal_range(data.begin(), data.end(),k);
        return resultPair.second - resultPair.first;
    }
};

发表于 2017-03-27 23:40:56 回复(12)
只是说排序数组,并没说升序还是降序,为啥都不判断,虽然给的测试用例都是升序的
发表于 2018-03-30 20:29:44 回复(3)
//由于数组有序,所以使用二分查找方法定位k的第一次出现位置和最后一次出现位置
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int lower = getLower(data,k);
        int upper = getUpper(data,k);
        
        return upper - lower + 1; 
    }
    
    //获取k第一次出现的下标
    int getLower(vector<int> data,int k){
        int start = 0,end = data.size()-1;
        int mid = (start + end)/2;
        
        while(start <= end){
            if(data[mid] < k){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
            mid = (start + end)/2;
        }
        return start;
    }
    //获取k最后一次出现的下标
    int getUpper(vector<int> data,int k){
         int start = 0,end = data.size()-1;
        int mid = (start + end)/2;
        
        while(start <= end){
            if(data[mid] <= k){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
            mid = (start + end)/2;
        }
        
        return end;
    }
};

编辑于 2017-02-22 21:53:00 回复(15)
class Solution {
    /*二分查找 找到第一个K 和 最后一个K 二者位置相减*/
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        int number = 0;
        int first = GetFirstIndex(data,k,0,data.size()-1);
        int last = GetLastIndex(data,k,0,data.size()-1);
        if(first>-1 && last>-1)
            number = last - first +1;
        return number;
        
    }
    int GetFirstIndex(vector<int> &data,int k,int start,int end){
        if(start > end)
            return -1;
        int mid = start+(end-start)/2;
        if(data[mid] == k){
            if((mid == start) || (data[mid-1] != k))
                return mid;
            else
                end = mid-1;
        }
        else{
            if(data[mid] > k)
                end = mid - 1;
            else
                start = mid + 1;
        }
        return GetFirstIndex(data,k,start,end);
    }
    int GetLastIndex(vector<int> &data,int k,int start,int end){
        if(start > end)
            return -1;
        int mid = start+(end-start)/2;
        if(data[mid]==k){
            if((mid == end) || (data[mid+1] != k))
                return mid;
            else
                start = mid +1;
        }
        else{
            if(data[mid]>k)
                end = mid-1;
            else
                start = mid+1;
        }
        return GetLastIndex(data,k,start,end);
    }
};

编辑于 2016-09-07 14:24:18 回复(17)

python solution


return data.count(k)

发表于 2017-10-13 22:18:03 回复(35)
//虽然有违出题人的本意,但是。。。
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
      //单纯的利用了count函数。。。。。
        return count(data.begin(),data.end(),k);
    }
};

发表于 2016-08-26 16:09:43 回复(19)
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        l = 0
        r = len(data)-1
        firstIndex  = self.getFirstIndex(data, k, l, r)
        lastIndex = self.getLastIndex(data, k, l, r)
        #print (lastIndex, firstIndex )
        return lastIndex - firstIndex + 1
        
    def getFirstIndex(self, data, k, l, r):
        #print (l,r)
        if l > r:
            return -1
        mid = int((r+l)/2)
        if data[mid] == k and (mid==0 or data[mid-1] != k):
            return mid
        else:
            if data[mid]>=k:
                return self.getFirstIndex(data, k, l, mid-1)
            else:
                return self.getFirstIndex(data, k, mid+1, r)
            
    def getLastIndex(self, data, k, l, r):
        while l<=r:
            #print(l,r)
            mid = int((l+r)/2)
            if data[mid] == k and (mid==len(data)-1 or data[mid+1] != k):
                return mid
            else:
                if data[mid] >k:
                    r = mid -1
                else:
                    l = mid+1
        return -2

发表于 2018-03-07 19:42:01 回复(1)
Python Solution: 书上的方法,二分法稍微改进一下
def GetFirstK(self, data, k):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] < k:
            low = mid + 1
        elif data[mid] > k:
            high = mid - 1
        else:
            if mid == low or data[mid - 1] != k: #当到list[0]或不为k的时候跳出函数
                return mid
            else:
                high = mid - 1
    return -1


def GetLastK(self, data, k):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] > k:
            high = mid - 1
        elif data[mid] < k:
            low = mid + 1
        else:
            if mid == high or data[mid + 1] != k:
                return mid
            else:
                low = mid + 1
    return -1


def GetNumberOfK(self, data, k):
    if not data:
        return 0
    if self.GetLastK(data, k) == -1 and self.GetFirstK(data, k) == -1:
        return 0
    return self.GetLastK(data, k) - self.GetFirstK(data, k) + 1

发表于 2018-10-10 20:26:19 回复(1)
/*
 * 受不了。。。。。。
 */
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
		int count=0;
    	for(int i=0;i<array.length;i++){
			if(array[i]==k)
				count++;
		}
    	return count;
    }
}

发表于 2016-08-23 15:34:54 回复(45)
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)
二分查找,参考剑指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)
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 回复(2)
有序序列,就使用二分查找的思路。一开始的思路是先使用二分法找到k,然后从k开始向两边统计k的个数,但统计的这个时间复杂度达到了O(n),导致整个算法的复杂度O(nlogn),而通过两次二分查找,分别找到第一个k和最后一个k,可以使时间复杂度减少为O(logn)
class Solution {
private:
    int findFirstK(const vector<int> &data, int k){
        int l = 0, r = data.size() - 1;
        int mid = (l + r) >> 1;
        while(l <= r){
            if(data[mid] > k){
                r = mid - 1;
            } else if(data[mid] < k){
                l = mid + 1;
            } else if(mid - 1 >= 0 && data[mid - 1] == k){
                r = mid - 1;
            } else{
                return mid;
            }
            mid = (l + r) >> 1;
        }
        return -1;
    }
    int findLastK(const vector<int> &data, int k){
        int l = 0, r = data.size() - 1;
        int mid = (l + r) >> 1;
        while(l <= r){
            if(data[mid] > k){
                r = mid - 1;
            } else if(data[mid] < k){
                l = mid + 1;
            } else if(mid + 1 < data.size() && data[mid + 1] == k){
                l = mid + 1;
            } else{
                return mid;
            }
            mid = (l + r) >> 1;
        }
        return -1;
    }
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int first = findFirstK(data, k);
        int last = findLastK(data, k);
        if(first == -1 || last == -1){
            return 0;
        }
        return last - first + 1;
    }
};

发表于 2017-08-13 23:21:38 回复(2)

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)
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的数组下标,然后通过下标分别向前和向后顺序搜索值为k的下标,由于是有序数组,相同元素在数组中是连续存放的,所以只要得到值为k的第一个下标和最后一个下标就可以了。
代码如下:
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()==0)
            return 0;
        int low=0,high=data.size()-1;
        int index = -1;
        while(low<=high){
            int mid = (low+high)>>1;
            if(data[mid]==k){
                index = mid;
                break;
            }
            else if(data[mid]>k)
                high = mid-1;
            else
                low = mid+1;
        }
        if(index==-1)
            return 0;
        low = index-1;
        high = index+1;
        while(low>=0 && data[low]==k)
            --low;
        while(high<data.size() && data[high]==k)
            ++high;
        return high-low-1;
    }
};

发表于 2016-03-29 20:28:22 回复(4)
/* 先用二分查找找出某个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)