你知道如何用代码去实现统计一个数字在排序数组中出现的次数吗?下面给大家带来了具体实例,一起来看看。
题目:
统计一个数字在排序数组中出现的次数。
思路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实例,可以继续来本站了解。