day5题目：
知识点：数组、二分、哈希，难度为中等、简单、简单
学习计划链接：
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
复制 [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
] 给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
思路及代码
思路1：二分法+一些优化
复制 /**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
if(matrix.length == 0) return false;
let [n, m] = [matrix.length, matrix[0].length];
for(let k = 0; k < n; ++k) {
if(matrix[k][0] > target)
break;
if(matrix[k][m - 1] < target)
continue;
let [l, r] = [0, m-1]
while(l <= r) {
let mid = (l+r)>>1;
if(matrix[k][mid] === target)
return true;
if(matrix[k][mid] > target) r = mid - 1;
else l = mid + 1;
}
}
return false;
}; 二叉搜索树中左边元素都比他小，右边元素都比他大，故这里若当前元素小于目标值则向右（实际是向下r++）找，大于目标值则向左（实际是向左c--）找。
复制 var findNumberIn2DArray = function(matrix, target) {
if(matrix.length == 0) return false;
let [n, m] = [matrix.length, matrix[0].length];
let [r, c] = [0, m - 1];
while(r < n && c >= 0) {
if(matrix[r][c] == target) return true;
else if(matrix[r][c] > target) --c;
else ++r;
}
return false;
}; 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 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 提示：
-5000 <= numbers[i] <= 5000
numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
思路及代码
因为可能有重复的元素，故此题还需注意重复元素处的 --r
复制 var minArray = function(numbers) {
if(numbers.length == 0) return 0;
let [l, r] = [0, numbers.length - 1];
while(l < r) {
let mid = (l + r) >> 1;
if(numbers[mid] > numbers[r]) l = mid + 1;
else if(numbers[mid] < numbers[r]) r = mid;
else --r;
}
return numbers[l];
}; 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
复制 输入：s = "abaccdeff"
输出：'b' 示例 2:
限制：
0 <= s 的长度 <= 50000
思路及代码
遍历一遍用哈希表存，出现过两次以上的都按两次算。
复制 var firstUniqChar = function(s) {
let m = new Map();
for (let i = 0; i < s.length; i++)
m.set(s[i], m.has(s[i]) ? 2 : 1);
for (let i = 0; i < s.length; i++)
if (m.get(s[i]) === 1)
return s[i];
return ' ';
}; 