剑指Offer-数字在排序数组中出现的次数

题目描述

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

思路

思路一:暴力,简单粗暴,但是并不可取

思路二:因为题中说是排序数组,因此我们要先想到二分查找,因此我们先用二分查找找出某个k出现的位置,然后再分别向前和向后查找总的个数。

思路三:还是二分查找的思想,先找到第一个k和最后一个k的位置相减

代码实现

package Array;

/**
 * 数字在排序数组中出现的次数
 * 统计一个数字在排序数组中出现的次数。
 */
public class Solution33 {
    public static void main(String[] args) {
        Solution33 solution33 = new Solution33();
        int[] array = {1, 3, 4, 5, 5, 6, 7, 8, 9, 10};
        System.out.println(solution33.GetNumberOfK_3(array, 5));
    }

    /**
     * 二分查找 找到第一个k和最后一个k二者位置相减
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK_3(int[] array, int k) {
        if (array == null || array.length == 0)
            return 0;
        int number = 0;
        int first = GetFirstIndex(array, k, 0, array.length - 1);
        int last = GetLastIndex(array, k, 0, array.length - 1);
        if (first > -1 && last > -1)
            number = last - first + 1;
        return number;
    }

    /**
     * 找到最后一个k的位置
     *
     * @param array
     * @param k
     * @param left
     * @param right
     * @return
     */
    private int GetLastIndex(int[] array, int k, int left, int right) {
        if (left > right)
            return -1;
        int mid = left + ((right - left) >> 1);
        if (array[mid] == k) {
            if (mid == right || (array[mid + 1] != k)) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else if (array[mid] > k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        return GetLastIndex(array, k, left, right);
    }

    /**
     * 找到第一个k的位置
     *
     * @param array
     * @param k
     * @param left
     * @param right
     * @return
     */
    private int GetFirstIndex(int[] array, int k, int left, int right) {
        if (left > right)
            return -1;
        int mid = left + ((right - left) >> 1);
        if (array[mid] == k) {
            if (mid == left || (array[mid - 1] != k)) {
                return mid;
            } else {
                right = mid - 1;
            }
        } else if (array[mid] > k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        return GetFirstIndex(array, k, left, right);
    }

    /**
     * 先用二分查找找出某个k出现的位置,然后再分别向前和向后查找总的个数
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK(int[] array, int k) {
        if (array.length == 0 || array == null)
            return 0;
        int left = 0;
        int right = array.length - 1;
        int count = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;//若数组过大,防止溢出
            if (array[mid] == k) {
                count++;
                //判断前面是否还有等于k的元素
                if (mid > left) {
                    if (array[mid - 1] == k) {
                        for (int i = mid - 1; i >= 0; i--) {
                            if (array[i] == k) {
                                count++;
                            } else break;
                        }
                    }
                }
                //判断后面是否还有等于k的元素
                if (mid < right) {
                    if (array[mid + 1] == k) {
                        for (int i = mid + 1; i <= right; i++) {
                            if (array[i] == k) {
                                count++;
                            } else break;
                        }
                    }
                }
                return count;
            } else if (array[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return 0;
    }


    /**
     * 暴力
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK_2(int[] array, int k) {
        if (array.length == 0 || array == null)
            return 0;
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                count++;
            }
        }
        return count;
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LanceToBigData

JavaSE(八)集合之Set

今天这一篇把之前没有搞懂的TreeSet中的比较搞得非常的清楚,也懂得了它的底层实现。希望博友提意见! 一、Set接口 1.1、Set集合概述   Set集合:...

2435
来自专栏desperate633

LintCode 乱序字符串题目分析代码

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

1103
来自专栏黑泽君的专栏

java基础学习_集合类03_用户登录注册案例(集合版)、Set集合、Collection集合总结_day17总结

============================================================================= ==...

1052
来自专栏Java进阶之路

一道有趣的Map迭代题

2110
来自专栏吾爱乐享

java之学习去除ArrayList中重复自定义对象元素

1756
来自专栏郭耀华‘s Blog

剑指offer第三天

21.栈的压入、弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,...

2966
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题37两个链表的第一个公共结点

本题的详细解析均在代码注释中: import java.util.Stack; /** * 题目:输入两个链表,找出他们的第一个公共结点 * @autho...

3175
来自专栏desperate633

Top 6 常见问题关于Java中的Map1 将Map转换成一个List2 遍历map中的键值对3 根据Map的key值排序4 根据Map的value值排序5 初始化一个静态的不可变的Map6 Has

我们都知道Map是一种键-值对的数据结构,每个键都是唯一的!本文讨论了关于Java中Map使用的最常见的8个问题。为了叙述的简单,所有的例子都会使用泛型。并且本...

813
来自专栏LinkedBear的个人空间

唠唠SE的集合-01——Collection接口

当集合中存储的对象类型不同时,那么会导致程序在运行的时候的转型异常,所以jdk1.5加入了泛型机制。

692
来自专栏武培轩的专栏

剑指Offer-和为S的两个数字

题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。 输出描述: 对应每...

3304

扫码关注云+社区

领取腾讯云代金券