剑指Offer JZ37 Python Solution

暴力解法

• 遍历数组

  # -*- coding:utf-8 -*-
  class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        cnt = 0
        for i in range(0,len(data)):
            if data[i] == k :
                cnt = cnt + 1
        return cnt

基于二分搜索算法的优化解法 （cite 剑指Offer）

• 利用非降序数组的特点简化二分搜索算法
  查找第一个与最后一个出现的数字k
  第一个数字k查找方法
  二分查找得到中间数字，若中间数字为k，判断中间数字的前一个数字，若前一个数字值小与k，利用数组非降序的特点，中间数字为第一个出现的k；若前一个数字值等于k，则第一个出现的数字出现在中间数字前，利用递归，寻找第一个出现的数字k。
  最后一个数字k查找方法
  中间数字若等于k，判断中间数字的后一个数字，若后一个数字值大于k，则中间数字为最后一个出现的k；若后一个数字等于k，则最后一个出现的数字出现在中间数字后，利用递归，寻找最后一个出现的数字k。
  特殊情况的处理
  数组index越界
• 功能测试（空数组，数组中无查找数字，查找数字在数组中出现一次/多次）
• 对于边界值测试用例的处理（数组中只有一个元素）
• Python Class Method

class Solution:
    def __init__(self):
        self.cnt = 0 
    def GetNumberOfK(self, data, k):
        # special case
        if len(data) == 0:
            return 0
        if len(data) == 1:
            if data[0] == k:
                return 1
            else:
                return 0

        start_index = 0
        end_index = len(data)-1
        # get the first_index of searched item k
        first_index = self.GetFirstK(data,k,start_index,end_index)
        print('first_index = '+ str(first_index))
        # get the last_index of searched item k 
        last_index = self.GetLastK(data,k,start_index,end_index)
        print('last_index = '+ str(last_index))

        return last_index - first_index + 1

    def GetFirstK(self, data, k, start_index, end_index):

        mid_index = int((start_index + end_index)/2)

        if mid_index == start_index:
            if data[mid_index] == k:
                return mid_index
            else:
                return -1


        if data[mid_index] == k:
            if data[mid_index-1] != k:
                return mid_index
            else:
                return self.GetFirstK(data, k, start_index, mid_index-1)
        elif data[mid_index] > k:
            return self.GetFirstK(data, k, start_index, mid_index-1)
        else:
            return self.GetFirstK(data, k, mid_index+1, end_index)


    def GetLastK(self, data, k, start_index, end_index):

        mid_index = int((start_index + end_index)/2)

        if mid_index == end_index:
            if data[mid_index] == k:
                return end_index
            else:
                return -2

        if data[mid_index] == k:
            if data[mid_index+1] != k:
                return mid_index
            else:
                return self.GetLastK(data, k, mid_index+1, end_index)
        elif data[mid_index] > k:
            return self.GetLastK(data, k, start_index, mid_index-1)
        else:
            return self.GetLastK(data, k, mid_index+1, end_index)