数组统计数字出现次数代码实现和思路

KLQ 2020-04-15 16:59:14 java常见问答 9594

你知道如何用代码去实现统计一个数字在排序数组中出现的次数吗?下面给大家带来了具体实例,一起来看看。

题目:

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

思路1:

因为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;
        }
};

思路2:

看见有序,那么基本上就可以肯定就是二分查找了,算法很简单,注意,不要拘泥于递归,要会循环写法。

代码实现:

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;
    }
}

思路3:

看到有序,就应该想到二分查找。

找到该数字在数组中第一次、最后一次出现的位置。

代码实现:

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;
    }
    private int getFirstK(int[] array, int k, int low, int high)
    {
        int mid = 0;
        while (low <= high)
        {
            mid = low + (high - low) / 2;
            if (array[mid] == k)
            {
                if (mid > 0 && array[mid - 1] != k || mid == 0)
                    return mid;
                else
                    high = mid - 1;
            }
            else if (array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
    private int getLastK(int[] array, int k, int low, int high)
    {
        int mid = 0;
        while (low <= high)
        {
            mid = low + (high - low) / 2;
            if (array[mid] == k)
            {
                if (mid < array.length - 1 && array[mid + 1] != k || mid == array.length - 1)
                    return mid;
                else
                    low = mid + 1;
            }
            else if (array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

数组统计数字出现次数的实现大家都有自己的想法了吗?更多Java实例,可以继续来本站了解。