在排序数组中查找数字.md

题目描述

数字在排序数组中出现的次数。

统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。

测试用例

• 功能测试（数组中包含要查找的数字；数组中没有要查找的数字；要查找的数字在数组中出现一次/多次）
• 边界值测试(查找数组中的最大值、最小值；数组中只有一个数字)
• 特殊输入测试（表示数组的指针为空指针）

题目考点

• 考察应聘者的只是迁移能力。
• 考察应聘者对二分查找算法的理解程度。

解题思路

一看到在排序数组中查找，大家一定能想到二分查找法，但是怎么用可以减少复杂度，that is problem.

1. 利用二分查找法找出最早(左)出现的k的下标
2. 利用二分查找法找出最晚(右)出现的k的下标

自己解题

/**
 * 在排序数组中查找数字
 * @Author rex
 * 2018/9/6
 */
public class Solution {
    /**
     * 垃圾算法，还是和普通遍历一样的复杂度
     * @param array
     * @param k
     * @return
     */
    public int getNumberOfK(int [] array , int k) {
        int count = 0;
        if (array == null || array.length == 0) {
            return count;
        }
        int index = getNumberOfKCore(array, k, 0, array.length - 1);
        int temp = index;
        while (temp >=0 && array[temp] == k) {
            count++;
            temp--;
        }
        temp = index + 1;
        while (temp <= array.length - 1 && array[temp] == k) {
            count++;
            temp++;
        }
        return count;
    }

    /**
     * 二分查找
     * @param array
     * @param k
     * @param start
     * @param end
     * @return
     */
    public int getNumberOfKCore(int[] array, int k, int start, int end) {
        if (start == end) {
            return start;
        }
        int mid = (start + end) >> 1;
        if (array[mid] < k) {
            return getNumberOfKCore(array, k, start, mid - 1);
        } else if (array[mid] > k){
            return getNumberOfKCore(array, k, mid + 1, end);
        } else {
            return mid;
        }
    }
}

参考解题

/**
 * 在排序数组中查找数字
 * @Author rex
 * 2018/9/6
 */
public class Solution1 {
    /**
     * 重复利用二分查找
     *
     * @param array
     * @param k
     * @return
     */
    public int getNumberOfK(int [] array , int k) {
        int count = 0;
        if (array == null || array.length == 0) {
            return count;
        }
        int first = getFirstK(array, k, 0, array.length - 1);
        int last = getLastK(array, k, 0, array.length - 1);
        if (first != -1 && last != -1) {
            count = last - first + 1;
        }
        return count;
    }

    /**
     * 找到第一个K的下标
     * @param array
     * @param k
     * @param start
     * @param end
     * @return
     */
    public int getFirstK(int[] array, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int middleIndex = (start + end) >> 1;
        int middleData = array[middleIndex];
        if (middleData == k) {
            if (middleIndex > 0 && array[middleIndex - 1] < k) {
                return middleIndex;
            } else {
                end = middleIndex - 1;
            }
        } else if (middleData > k) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getFirstK(array, k, start, end);
    }

    /**
     * 找到最后一个K的下标
     * @param array
     * @param k
     * @param start
     * @param end
     * @return
     */
    public int getLastK(int[] array, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int middleIndex = (start + end) >> 1;
        int middleData = array[middleIndex];
        if (middleData == k) {
            if (middleIndex < array.length - 1 && array[middleIndex + 1] > k) {
                return middleIndex;
            } else {
                start = middleIndex + 1;
            }
        } else if (middleData < k) {
            start = middleIndex + 1;
        } else {
            end = middleIndex - 1;
        }
        return getLastK(array, k, start, end);
    }
}

补充

看到排序数组就应该想到二分查找法，但是在判断的时候需要灵活变通。