LeetCode：Search Algorithm

1\First unique char

Algorithm Design

利用字符数量的有限性，通过数组来映射(避免Hash_map的高复杂度)

注意数组声明为int A[26]而不是char A[26];

if(s=="") return ' ';
 	 int A[26]={0,0};
 	 for(int i=0;i<s.length();i++){
 	     A[s[i]-0x61]++;
 	 }
 	 for(int i=0;i<s.length();i++){
 	     if(A[s[i]-0x61]==1){
 	         return s[i];
 	     }
 	 }        
 	 return ' ';

Dict/Hash_map

	unordered_map<char,int> map;
     for(auto i:s){
         map[i]++;
     }
     for(auto i:s){
         if(map[i]==1){
             return i;
         }
     }
     return ' ';

dic[c] = dic.find(c) == dic.end();

	unordered_map<char, bool> dic;
    for(char c : s)
    dic[c] = dic.find(c) == dic.end(); //很有意思的写法
    for(char c : s)
        if(dic[c]) return c;
    return ' ';

2\Min(Rotated Array)

Algorithm Design

两个有序升序数组，前一个比后一个大；
可以通过nums[mid]>nums[left]判断后left=mid+1(这里nums[mid]不可能是结果所以mid+1)
也可通过nums[mid]<nums[right]后right=mid(这里nums[mid]可能是结果所以right=mid;
后者更好因为题目要求可以适应旋转量为0，如图，那么后者可以使得right不断左移到达min处；

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l=0,r=numbers.size()-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(numbers[mid]<numbers[r]){
                r=mid;
            }else if(numbers[mid]>numbers[r]){
                l=mid+1;
            }else{
                r--;
            }
        }
        return numbers[r];
    }
};
//  3 4 5 5 5 5 5 5 5 0 0 0 1 2 2 2 2 2 2 
// 3 4 5 1 2

3\Search in Ordered Martix

Algorithm Design

Z字形找，从左下或右上开始

可以理解为左下角的数是该行的最小值，该列的最大值。所以如果target比左下角还小，则肯定比这一行都小，所以可以上移一行寻找；如果target比左下角还大，则肯定比这一列都大，所以可以右移一列寻找

         //左下
		 if(matrix.empty()) return false; //注意先检查
		 int i=matrix.size()-1,j=0;
         while(j<matrix[0].size()&&i>=0){
             if(matrix[i][j]==target){
                 return true;
             }else if(matrix[i][j]<target){
                 j++;
             }else{
                 i--;
             }
         }
         return false;

局部二分

    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(auto row:matrix){
            // auto have_target=find_if(row.begin(),row.end(),[&target](auto x){return x==target;});
            // if(have_target!=row.end()) return true;
             auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }