文章目录

1、题目描述2、解题思路2.1 暴力遍历2.2 二分查找2.3 插值查找2.4 斐波那契查找 3、解题代码3.1 暴力遍历3.2 二分查找3.3 插值查找3.4 斐波那契查找 4、解题心得

1、题目描述

  【JZ37】统计一个数字在排序数组中出现的次数。   知识点：数组，查找算法   难度：☆

2、解题思路

  本题其实就是考察查找算法，常用的查找算法有：暴力遍历、二分查找、插值查找和斐波那契查找。   设数组为array，目标数字为k。

2.1 暴力遍历

  因为数组是有序的，所以我只需要一个个去遍历即可，比较简单。需要注意的是，遍历找到相同的数字时，因为是有序数组，后面可能跟着若干个一样的数字，因此，统计好相同数字的个数后要结束算法，后面再遍历下去没有意义。

2.2 二分查找

  二分查找的思路就是不断缩减待查询的数组长度。假设数组长度为10，那么，一开始的左边界就是0，右边界是9。中间索引为(0+9)/2，为4，若array[4]<k，说明k在数组的右半截，我们就把右半部分当成新数组，就不去考虑左边的部分，节省了一半的计算量。   以此类推，不断缩减数组范围，直到array[4]==k，就找到了。如果缩减到数组长度为0都找不到，则不存在目标数字。

2.3 插值查找

  插值查找是在二分查找的基础上优化的，与二分查找的不同之处在于中间值的计算方式：   相比较于二分查找，插值查找能够更快速接近目标值。

2.4 斐波那契查找

  斐波那契查找和上面两个查找的不同之处也在于mid值的计算，斐波那契数列的特点是，第一个元素和第二个元素都为1，以后每个元素都等于前两个元素之和，比如：{1,1,2,3,5,8,13,21,...}。   那如何根据斐波那契数列来计算mid呢？   假设array的长度为10，那么，我们要把中间某个位置设为mid，然后分为mid前部分和mid后部分。   首先把array长度扩充为最接近的斐波那契数列元素，现在长度为10，斐波那契数列中，比它大且最接近的，只能是13。array的索引是0到9，那么，拓展的10-12的值从索引9的值复制。   根据斐波那契数列的特点，13=8+5，所以把array分成前8个和后5个两部分，而这个mid就是前部分的最后一个元素（或者后部分的第一个元素），即所谓的黄金分割点。   找到mid后，其他计算和前面的二分和插值是一样的。   因为索引是从0开始的，所以长度为F[k]的数组，起索引范围为0到F[k]-1。   由图可知，mid = low + F[k-1]-1。   也就是说，mid的取值，和两个值有关，low和F[k-1]，low也就是左边界，F[k-1]为F[k]的前一个值。   在计算mid之前，我们需要把要用到的斐波那契数列计算出来。   为了方便起见，我们生成的斐波那契数列元素个数和array元素个数一致即可。

3、解题代码

3.1 暴力遍历

package pers.klb.jzoffer.medium; /** * @program: JzOffer2021 * @description: 数字在排序树组中出现的次数 * @author: Meumax * @create: 2020-07-04 20:06 **/ public class NumberOfK { public int GetNumberOfK(int[] array, int k) { int count = 0; for (int i = 0; i < array.length; i++) { if (array[i] == k) { int j = i; while (j < array.length && array[j] == k) { count++; j++; } break; } } return count; } }

  时间复杂度：O(N)   空间复杂度：O(1)

3.2 二分查找

package pers.klb.jzoffer.medium; /** * @program: JzOffer2021 * @description: 数字在排序树组中出现的次数 * @author: Meumax * @create: 2020-07-04 20:06 **/ public class NumberOfK { // 二分查找 public int GetNumberOfK(int[] array, int k) { int count = 0; // 重复次数 int leftIndex = 0; // 左索引 int rightIndex = array.length - 1; // 右索引 int mid; int index = -1; // 目标数字在array中的其中一个位置 // 找到目标数字所在的其中一个位置 while (leftIndex <= rightIndex) { mid = midOf(leftIndex, rightIndex); if (array[mid] < k) { leftIndex = mid + 1; } else if (k < array[mid]) { rightIndex = mid - 1; } else { // k == array[mid] index = mid; break; } } // 找到其中一个数字后，往前和往后统计出现了多少次 if (index != -1) { count = 1; // 往前统计 for (int i = index - 1; i >= 0; i--) { if (array[i] == k) { count++; } } // 往后统计 for (int j = index + 1; j < array.length; j++) { if (array[j] == k) { count++; } } } return count; } private int midOf(int left, int right) { return (left + right) / 2; } }

  时间复杂度：O(logN)   空间复杂度：O(1)

3.3 插值查找

package pers.klb.jzoffer.medium; /** * @program: JzOffer2021 * @description: 数字在排序树组中出现的次数 * @author: Meumax * @create: 2020-07-04 20:06 **/ public class NumberOfK { // 插值查找 public int GetNumberOfK(int[] array, int k) { int count = 0; // 重复次数 int leftIndex = 0; // 左索引 int rightIndex = array.length - 1; // 右索引 int mid; int index = -1; // 目标数字在array中的其中一个位置 // 找到目标数字所在的其中一个位置 while (leftIndex <= rightIndex) { mid = midOf(array, leftIndex, rightIndex, k); if (array[mid] < k) { leftIndex = mid + 1; } else if (k < array[mid]) { rightIndex = mid - 1; } else { // k == array[mid] index = mid; break; } } // 找到其中一个数字后，往前和往后统计出现了多少次 if (index != -1) { count = 1; // 往前统计 for (int i = index - 1; i >= 0; i--) { if (array[i] == k) { count++; } } // 往后统计 for (int j = index + 1; j < array.length; j++) { if (array[j] == k) { count++; } } } return count; } // 插值查找的中间值计算 private int midOf(int[] arr, int left, int right, int key) { if (arr[left] == arr[right]) { return left; } else { return left + ((key - arr[left]) / (arr[right] - arr[left])) * (right - left); } } }

  时间复杂度：O(loglogN)   空间复杂度：O(1)

3.4 斐波那契查找

package pers.klb.jzoffer.medium; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * @program: JzOffer2021 * @description: 数字在排序树组中出现的次数 * @author: Meumax * @create: 2020-07-04 20:06 **/ public class NumberOfK { // 插值查找 public int GetNumberOfK(int[] array, int k) { int count = 0; // 重复次数 if (array.length == 1) { if (array[0] == k) count = 1; } else { int low = 0; // 左索引 int high = array.length - 1; // 右索引 int mid; int index = -1; // 目标数字在array中的其中一个位置 List<Integer> f = fib(array.length); // 斐波那契数组 int s = f.size() - 1; // s为待搜索数组长度所对应的斐波那契数组的数的下标 int[] arr1 = Arrays.copyOf(array, f.get(s)); // 新建一个数组，长度为斐波那契数组第k个索引对应的数 // 如果初始待搜索数组长度不是对应斐波那契数组某个数，那就填充到对应上 for (int i = array.length; i < s; i++) { arr1[i] = array[array.length - 1]; } // 找到目标数字所在的其中一个位置 while (low <= high) { mid = midOf(low, f.get(s - 1)); // 斐波那契查找法计算出的中间值 if (arr1[mid] < k) { s = s - 2; low = mid + 1; } else if (k < arr1[mid]) { s = s - 1; high = mid - 1; } else { // k == arr1[mid] // arr1是从arr拷贝过来的，后面是重复值，所以要确定返回哪一个下标 if (mid <= high) { index = mid; } else { index = high; } break; } } // 找到其中一个数字后，往前和往后统计出现了多少次 if (index != -1) { count = 1; // 往前统计 for (int i = index - 1; i >= 0; i--) { if (array[i] == k) { count++; } } // 往后统计 for (int j = index + 1; j < array.length; j++) { if (array[j] == k) { count++; } } } } return count; } // 斐波那契查找的中间值计算 private int midOf(int low, int f) { return low + f - 1; } // 生成斐波那契数组 private List<Integer> fib(int arrLength) { List<Integer> f = new ArrayList<Integer>(); f.add(0, 1); for (int i = 1; f.get(f.size() - 1) < arrLength; i++) { if (i == 1) { f.add(i, 1); } else { f.add(i, f.get(i - 1) + f.get(i - 2)); } } return f; } }

4、解题心得

  暴力遍历是每个人都能想得到的，如果在笔试的时候，使用二分查找既可以快速求解，难度也不会太高。如果是面试，能实现插值查找就最好了，斐波那契查找能说出原理也是OK的。但是不建议在笔试的时候用斐波那契查找，第一是比较复杂，第二点性能相比插值查找相差不远。