二維陣列中查找

題目描述

思路

• 遍歷法

只要是這種查找的題都有一個通解就是遍歷，顯然如果是面試那么offer就要👋了，代碼自行寫，本質就是一個二維陣列

• 利用條件法(瞎取的)

從題可以看出每一行都是左右遞增，每一列都是上下遞增，那么我們就可以利用這個特性，


target和第一行的最后一個元素比，那么會出現倆種狀況

1. targe大于最后元素
   因為是左右遞增，那么targe就不會在當前行，直接排除當前行
   
   
2. targe小于最后元素
   因為是上下遞增那targe就不在當前列，直接排除當前列

代碼：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) 
    {
        //1.查找本質就是排除
        //2.陣列從左到右、從上到下都是遞增的
        //3.利用這一特性就可以一次排除一行或者一列
        
        int  row =0;//行
        int  lin=array[0].size()-1;//列
        while(row<array.size()&&lin>=0)
        {
            if(array[row][lin]<target)//小于說明不在這一行
            {
                row++;
            }
            else if(array[row][lin]>target)//大于說明不在這一列
            {
                lin--;
            }
             else
             {
                    return true;//上面的情況都不是說明找到了
             }
        }
        return false;//回圈下來沒有找到說明沒有
    }
};

題目鏈接

旋轉陣列中最小的數字

題目描述

思路

• 遍歷
• sort排序(利用庫)
• 雙指標遍歷(利用條件)

題說是非降序的陣列，且是旋轉過來的如 1，2，3，4 --> 3，4，1，2可以看出如果相鄰的倆個數前一個比后一個大那么那個值就是最小數，但是這個本質也是遍歷，就是少走幾次回圈罷了

代碼：

 class Solution {
public://雙指標法
    int minNumberInRotateArray(vector<int> rotateArray)
    {
        int prev=0;
        int next=1;
        if(rotateArray[prev]<rotateArray[next]&&rotateArray[next]==rotateArray[rotateArray.size()-1])//處理特殊情況，只有倆個資料，或者只有一個資料的情況
        {
            return rotateArray[prev];
        }
         while(next<rotateArray.size())
         {
             if(rotateArray[prev]>rotateArray[next])
             {
                 break;
             }
             prev=next++;
         }
        return rotateArray[next];
        
    }
};

• 二分查找法(利用條件)

同樣利用非遞減，旋轉這倆個條件，數列：4，5，1，2，3
思路如圖所示：

代碼：

class Solution
{
public://二分法
     int minNumberInRotateArray(vector<int> rotateArray)
       {
         int left=0;
         int right=rotateArray.size()-1;
         
         while(left<right)//條件
         {
           if(rotateArray[left]<rotateArray[right])//特殊情況[1,2,2,2,2],這個也叫非遞減，，，，,也可以把判斷寫在二分失效這，建議寫著效率高
           {
               return rotateArray[left];
           }
              if(left+1==right)//當左右left與right相鄰時right一定是最小值
                  {
                      break;
                  }
             int middle=(left+right)/2;
              if(rotateArray[left]==rotateArray[right]&&rotateArray[right]==rotateArray[middle])//該數列中多個重復數字，二分法失效
               {
                  int mini=rotateArray[left++];
                  while(left<=right)
                  {
                      if(rotateArray[left]<mini)
                      {
                          mini=rotateArray[left];
                      }
                      left++;
                  }
                  return mini;
               }
             if(rotateArray[left]<=rotateArray[middle])//reft～middle屬于一個區間
             {
                 left=middle;
             }
             else
             {
                 //middle~right屬于一個區間
                 right=middle;
             }
         }
         return rotateArray[right];
       } 
};

上述思路中推薦使用二分法，你如果覺得不好把控，你可以寫雙指標法，那么面試官會覺得你利用了原有條件，會給你加分，實在沒有看出來你也可以使用sort，順便問問面試官可不可以呼叫系統的介面，不行的話你在秀一下自己寫快排的能力面試官看你寫的不錯也會給你加分，但是寫出二分法offer到手

題目鏈接

陣列中出現次數超過一半的數字

題目：

思路

• 排序取中值

題目說，一定會有解，那么一個值出現一半那么拍完序，那么中間部分的值一定就是你要找的值

• 塔防法

看著名字是不是很不一樣哈哈哈，其實也可以叫保衛蘿卜法


1. 選取第一個數字為弓箭手，且他有一個血條初始值1


2 .遇到相同數則加血，不同則扣血，當血被扣完時，誰殺死“弓箭手”，誰就是新的弓箭手，如此往復


3. 預防陣列中沒有值出現次數超過一半長度的值

代碼：

//塔防法
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        int guard=numbers[0];
        int hp=1;
       for(int i =1;i<numbers.size();i++)//尋找幸存的弓箭手
       {
            if(numbers[i]==guard)
            {
                hp++;
            }
            else
            {
                hp--;
            }
           if(hp==0)//更換哨兵
            {
               guard=numbers[i];
               hp=1;
            }
       }
        int count=0;
     for(int i =0;i<=numbers.size();i++)//判斷是否存在，可以不寫題目標注一定有解
     {
         if(numbers[i]==guard)
         {
             count++;
         }
     }
       return count>numbers.size()/2?guard:0;
    }
};

題目鏈接

絮絮叨叨的家常

這篇博客之后你需要認識一個概念就是查找的本質就是排除，效率高就是一次排除的多（二分），效率低（遍歷）