算法复习:数字在排序数组中出现的次数

xiaoxiao2021-02-28  62

题目描述

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

解题思路

(1)遍历一次求出个数 (2)使用二分查找求出第一个和最后一个的下标。如何求第一个数字呢,假如要找的数字和中间的数字相等,则判断其前面一个数字(下标不越界),假如不相等则是第一个数字。同理可求最后一个数字。需要注意的是数组下标越界问题。

代码:

public static int GetNumberOfK(int[] array, int k) { int number = 0; if (array != null && array.length > 0) { int firstK = getFirstK(array, k); int lastK = getLastK(array, k); if (firstK > -1 && lastK > -1) return lastK - firstK + 1; } return number; } public static int getFirstK(int[] array, int k) { int start = 0; int end = array.length - 1; int middle; while (start <= end) { middle = (start + end) / 2; int middleNum = array[middle]; if (middleNum == k) { if ((middle > 0 && (array[middle - 1] != k)) || middle == 0) { return middle; } else { end = middle - 1; } } else if (middleNum < k) { start = middle + 1; } else { end = middle - 1; } } return -1; } public static int getLastK(int[] array, int k) { int start = 0; int end = array.length - 1; int middle; while (start <= end) { middle = (start + end) / 2; int middleNum = array[middle]; if (middleNum == k) { if ((middle < end && (array[middle + 1] != k)) || middle == end) { return middle; } else { start = middle + 1; } } else if (middleNum < k) { start = middle + 1; } else { end = middle - 1; } } return -1; }
转载请注明原文地址: https://www.6miu.com/read-79587.html

最新回复(0)