剑指Offer（三十七）：数字在排序数组中出现的次数（C++/Python）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指Offer（三十七）：数字在排序数组中出现的次数（C++/Python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1782字，纯文字阅读大概需要3分钟。

内容图文

题目描述

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

解题思路

找到该数字在数组中第一次和最后一次出现的下标，即可求得次数。为提高时间效率，利用二分法查找。

相比以往的查找某个元素的位置不同的是：

对firstpos来讲，当当前的mid处的值等于k，且mid为数组第一个元素或者，mid处的前一个值不为k，则mid为firstpos

对endpos来讲，当当前的mid处的值等于k，且mid为数组最后一个元素或者，mid处的后一个值不为k，则mid为endpos

C++版

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.size() == 0 || k < data[0] || k > data[data.size() - 1])
            return 0;
        int cnt = 0, low = 0, high = data.size() - 1, lastpos, firstpos = -1;
        while(low <= high){
            int mid = (high + low) >> 1;
            if(data[mid] == k){
                if(mid > 0 && data[mid-1] != k || mid == 0){
                    firstpos = mid;
                    break;
                }
                else
                    high = mid - 1;
            }
            else if(data[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        if(firstpos == -1)
            return 0;
        low = 0;
        high = data.size() - 1;
        while(low <= high){
            int mid = (high + low) >> 1;
            if(data[mid] == k){
                if(mid == data.size() - 1 || (mid < data.size() - 1 && data[mid+1] != k)){
                    lastpos = mid;
                    break;
                }
                else
                    low = mid + 1;
            }
            else if(data[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return lastpos - firstpos + 1;
    }
};

Python版

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if len(data) == 0 or data[0] > k or data[-1] < k:
            return 0
        firstpos, lastpos = -1, -1
        low, high = 0, len(data) - 1
        while low <= high:
            mid = (low + high) / 2
            if data[mid] == k:
                if mid == 0 or data[mid-1] != k:
                    firstpos = mid
                    break
                else:
                    high = mid - 1
            elif data[mid] > k:
                high = mid - 1
            else:
                low = mid + 1
        if firstpos == -1:
            return 0
        low, high = 0, len(data) - 1
        while low <= high:
            mid = (low + high) / 2
            if data[mid] == k:
                if mid == len(data) - 1 or data[mid+1] != k:
                    lastpos = mid
                    break
                else:
                    low = mid + 1
            elif data[mid] > k:
                high = mid - 1
            else:
                low = mid + 1
        return lastpos - firstpos + 1

内容总结

以上是互联网集市为您收集整理的剑指Offer（三十七）：数字在排序数组中出现的次数（C++/Python）全部内容，希望文章能够帮你解决剑指Offer（三十七）：数字在排序数组中出现的次数（C++/Python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端