[数据结构与算法]剑指Offer（LeetCode）查找算法，不断更新ing.............

博主刷题记录题型，刷到的题型会记录下来，不断更新ing-------------------------------
既然来了就给博主一个关注吧，希望能帮助到进来的您 ?

看到数组 就想能不能用二分做！！！

剑指 Offer 53 - I. 在排序数组中查找数字 I

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

示例 1:
输入: nums = [5,7,7,8,8,10] target = 8
输出: 2

示例 2:
输入: nums = [5,7,7,8,8,10] target = 6
输出: 0

当我们看到题目表述中出现排序数组第一反应就想能不能使用二分查找去做，一般算法题中出现排序数组大多数都希望用二分查找去做

解题分析：

1. 既然是排序数组，那他给定的数字在数组中就是相邻的两个数字
2. 使用二分法定区间 当大于中间位置的数组 left = mid+1 小于中间位置 right = mid-1
3. 刚好是中间的数字，需要特殊处理，因为我们不知道左边和右边有没有数字，所以我们需要判断数组左右等不等于该数字。如果等于我们就break
4. 最红我们要输出的是right -left区间的数字个数 并且+1得到最终结果

上代码！！！

 public int search(int[] nums, int target) {
   	  int length = nums.length;
      int left = 0;
      int right = length - 1;
      while (left <= right) {
      	 //找到中间位置
          int mid = left + (right - left) /2;
          //查找target位置区间
          if (nums[mid] < target) {
              left = mid+1;
          }else if (nums[mid] > target) {
              right = mid -1;
          }else {
          	 // 当找到target位置时，我们在次判断左右有没有
              if (nums[left] != target) {
                  left++;
              }else if (nums[right] != target){
                  right--;
              }else {
                  break;
              }
          }
      }
   return right - left+1;
}

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers
，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为
[1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1],
a[2], …, a[n-2]] 。

示例 1：

输入：numbers = [3,4,5,1,2]
输出：1

示例 2：

输入：numbers = [2,2,2,0,1]
输出：0

简单来说就是找到最小的数字，只不过题中已经是旋转过的，典型的二分查找。
可不敢硬遍历！！！
可不敢调用排序！！！
咱虽然说两种做法合理合法，面试官ps：弄撒捏！！！ 传事里？？?

话不多说，上代码！！！

   public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;

        while (left <= right) {
            int mid = left +(right - left) / 2;
            //前边都是二分定义模板
            //当中间的数字 大于 右边的数字时
            //说明左边都大于这个数字，所以左边的数字来到mid加1的位置
            if (numbers[mid] > numbers[right]) {
                left = mid+1;
                //中间小于右边的时候，有边界来到中间这个数组的位置
            }else if (numbers[mid] < numbers[right]) {
                right = mid;
            }else {
                right--;
            }
        }
        //来到的都是最小的位置
        return numbers[left];
    }

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1
的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

当大家看到题目中“重复”、“数组” 就会想到二分、Hash进行解题，这道题呢可以使用二分解决问题，也可使用Map、Set解题。解题思路会写在题中

public int findRepeatNumber(int[] nums) {
	Map<Integer,Integer> map = new HashMap<>();
	//遍历
	for (int num : nums) {
		//当map中已经包含某个数字时候 直接return出该数字
		if (map.containsKey(num)) {
			return num;
		}else {
			//map中没有出现该数字，就往map中加入
			map.put(num, 1);
		}
	}
	return -1;
}

Map解法和Set解题方法一致

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:
输入：s = “abaccdeff”
输出：‘b’

示例 2:
输入：s = " "
输出：’ ’

该题在字符串中也是较为简单的同样也有多种方法解题比如：计数器、字典、Hash等
上代码！！！ 题解写在代码中

	public char firstUniqChar(String s) {
           //判空 字符串为空的时候 直接返回空
        if (s.length()==0 || "".equals(s)) {
            return ' ';
        }

        Map<Character , Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            //getOrDefault 当map有这可key时，就使用key对应的value值 如果没有就是用key的默认值,
            //这里我们默认值给0，出现的时候加1
            map.put(c,map.getOrDefault(c,0)+1);
        }

        for (char c : chars) {
            //再次遍历，找key值为1的 第一次出现的字符 输出即可
            if (map.get(c)==1) {
                return c;
            }
        }
        return ' ';
    }