手撕代碼之查找問題

文章目錄

• 旋轉數組找最小
• [1,n]整數數組中找1出現的總個數
• 在二維數組中查找值

旋轉數組找最小

題目描述： 輸入一個旋轉數組，找出這個數組中的最小值，要求時間複雜度為(logn)

題目分析：

• 旋轉數組：指的是将一個有序的數組的前一部分移動到後一部分，如[1,2,3,4,5]的一個旋轉數組為：[2,4,5,1,2]
• 時間複雜度為logn:立刻想到二分法(折半查找)

• 二分查找一般需要個固定的比較值，然而這道題卻沒有，怎麼辦？根據題意具體分析有以下幾種情況：

  （1）[4,5,6,1,2,3],arr[mid]>arr[first],故min在區間[mid+1,last]

  （2）[4,5,1,2,3] arr[mid]< arr[last],故min在區間[first,mid]

  （3）[1,1,1,0,1],則，first,向左移動一位；

  代碼

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0){
            return 0;
        }
        int i=0;//首元素
        int j=array.length-1;
        while(i<j){
            if(array[i]<array[j]){//沒有進行旋轉的一種特殊情況
                return array[i];
            }
            int mid=(i+j)/2;
            if(array[i]<array[mid]){
                //要找的最小值必然在右半部分
                i=mid+1;
            }else if(array[j]>array[mid]){
                j=mid;
            }else{
                i++;
            }
        }
        //特例：隻有一個元素
        return array[i];
    }
}
           

[1,n]整數數組中找1出現的總個數

題目描述： 求出113的整數中1出現的次數,并算出1001300的整數中1出現的次數？為此他特别數了一下1~13中包含1的數字有1、10、11、12、13是以共出現6次,但是對于後面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數）。

解題思路：

從最低位向最高位依次取出目前值cur，并計算cur的高位high和低位low;

當cur == 0時，出現的1的個數=highi;

當cur ==1時，出現1的個數=highi+(low+1);

其他情況，出現1的個數=(high+1)*i;

最後計算從最低位到最高位的總和

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i=1;i<=n;i*=10){
            int high=n/(i*10);
            int low=n%i;
            int curVal=n/i%10;
            if(curVal==0){
                count+=high*i;
            }else if(curVal==1){
                count+=high*i+(low+1);
            }else{
                count+=(high+1)*i;
            }
        }
        return count;
    }
}
           

在二維數組中查找值

題目描述： 在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

題目分析：

從左下角元素(curVal)開始尋找，這個元素是這行中最大的數，這列中最小的數，如果target>curVal,隻能從下一列中開始尋找，即col++,如果target< curVal，隻能從上一行中尋找，即row–；注意 col<=cols-1;row>=0;

public class Solution {
    public boolean Find(int target, int [][] array) {
        //最後一列的中間值
        int rows=array.length;//二維數組的行數
        int cols=array[0].length;//二維數組的列數
        if(rows==0){
            return false;
        }
        if(cols==0){
            return false;
        }
        //左下角
        int row=rows-1;
        int col=0;
        while(row>=0 && col<=cols-1){
            if(array[row][col]<target){
                col++;
            }else if(array[row][col]>target){
                row--;
            }else{
                return true;
            }
        }
        return false;
    }
}