《劍指offer》專題—演算法訓練 day01

??從今天起，博主開始了 《 劍指offer 》 系列 演算法專題的學習，希望大家 跟隨著博主一起，開始這段美妙的演算法之旅…

一、二維陣列的查找

題目鏈接：

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?

思路一

暴力演算法

分析：直接遍歷一遍陣列，即可判斷目標target是否存在，

public class Solution {

    public boolean Find(int target, int [][] array) {
    
    // 先for 回圈遍歷一下 陣列的每一行
    
        for(int i = 0;i<array.length;i++){
    
        // 再 for 回圈遍歷一下陣列這一行的每一列
    
            for(int j = 0;j<array[0].length;j++){
    
            // 判斷每一個元素是否是我們需要的target
    
                 if(array[i][j] == target){
                     return true;
                 }
            }
            
        }
                    return false;
    }
}

思路二

查找的程序 本質是 排除的 程序

我們用暴力演算法 一次只能排除一個，效率很低

我們可以利用這個題中矩陣的性質

每一行從左到右依次遞增

每一列從上到下依次遞增

我們會發現右上角的值 是所在行中最大的，同時也是所在列中 最小的.

那么我們每次查找 target 值時，都與這個矩陣 右上角的值進行比較

如果 小于 右上角，那么可以排除這一列

如果 大于 右上角 ， 那么可以排除這一行

好了，我們根據這個思路可以寫出代碼：

public class Solution {
    public boolean Find(int target, int [][] array) {
      int i = 0;
      int j = array[0].length-1;
        
        while(i<=array.length-1 && j>=0){
            
//             array[i][j]一定是當前行最大，當前列最小的數
//              target < array[i][j] 排除當前列
            
            if(target<array[i][j]){
                j--;
                
//                 target> array[i][j] 排除當前行
            
            }else if(target >array[i][j]){
                i++;
                
//                 target == array[i][j] 此時找到 對應元素，回傳true
            
            }else{
                return true;
            }
        }
        
//         如果回圈跳出，那么說明沒有找到對應的元素，此時回傳 false
        
        return false;
    }
}

二、旋轉數字的最小數字

題目鏈接：

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?

思路一

本質其實是一個求最小值問題

理論上，遍歷一次即可

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        
        if(array == null || array.length == 0){
            return 0;
        }
        
        int min = array[0];
        
        for(int i = 1;i<array.length;i++){
            if(min>array[i]){
                min = array[i];
            }
        }
        
        return min;
    }
}

思路二

按照要求，要么是一個非遞減排序的陣列（最小值在最開始），要么是一個旋轉(最小值在中間某個地方)

而且，旋轉之后有個特征，就是在遍歷的時候，原始陣列是非遞減的，旋轉之后，就有可能出現遞減，引起遞減的數字，就 是最小值

采用二分查找的方式，進行定位

定義首尾下標，因為是非遞減陣列旋轉，所以旋轉最后可以看做成兩部分，前半部分整體非遞減，后半部分整體非遞減，前 半部分整體大于后半部分，

所以，我們假設如下定義，left指向最左側，right指向最右側，mid為二分之后的中間位置，

則，a[mid] >= a[left],說明mid位置在原陣列前半部分，進一步說明，目標最小值，在mid的右側，讓left=mid

a[mid] < a[left], 說明mid位置在原陣列后半部分，進一步說明，目標最小值，在mid的左側，讓right=mid

這個程序，會讓[left, right]區間縮小

這個程序中，left永遠在原陣列前半部分，right永遠在原陣列的后半部分，而范圍會一直縮小

兩種情況：

當left和right相鄰時，right指向的位置，就是最小元素的位置

但是，因為題目說的是非遞減，也就意味著資料允許重復，因為有重復發，就可能會有arr[left] == arr[mid] == arr[right]的情況，我們就無法判定資料在mid左側還是右側，（注意，只要有兩者不相等，我們就能判定應該如何縮小范圍）

相關代碼：

//  二分查找

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
      
      // 判斷陣列是否為空 以及 陣列內容是否為空
        
        if(array == null || array.length == 0){
            return 0;
        }
        
        int left = 0;
        int right = array.length-1;
        int mid = 0;
        
        while(array[left]>=array[right]){
          // 這里的回圈條件是 因為是旋轉陣列所以左區間最小的值 大于等于右區間最大的值                

          
          // 這種 情況是 當區間縮小到只有兩個元素是，右邊那個是最小的數字
          if(right-left ==1){
                mid = right;
                break;
            }
            
            mid = (left +right)/2;
          
          // 這種情況是 當 左 中 右 三值都相等時，我們無法判斷 mid下標元素在左區間還是右區間
          // 我們只能從頭遍歷，查找陣列中的最小值
          
            if(array[left] == array[mid] && array[mid] == array[right]){         
                int result = array[left];
                
                for(int i = left+1;i<right;i++){
                  
      // 我們不需要從 left 開始遍歷 ，還有最后 不用 <= right，因為 arr[left] = arr[right] ,我們不用再去判斷         
                  if(array[i]<result){
                        result = array[i];
                    }
                  
                }
                
                return result;
                
            }
            
 //下面的這個判斷就是 mid元素 大于 left元素，那么mid 在左區間，而我們要查找的最小數字在右區間,所以left=mid,縮小區間
          
            if(array[mid]>=array[left]){
                left = mid;
            }else{
                right = mid;
            }
        }
     
      // 最后回傳 mid下標的元素
      
        return array[mid];
    }
}

三、奇偶互換

題目鏈接：

https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?

??大家做這種題目一定要看好，調換奇數和偶數的時候 ，有沒有說明 相對位置是否發生改變.

??當然了，這道題原題是不需要保證奇偶位置不變的，先給大家說一下 相對位置發生改變的題目.

相對位置變化

思路

給大家說一下思路：

左右指標法

我們需要定義一個 左指標 和右指標 分別從 陣列的兩頭進行遍歷.

在一個 left < right 的一個回圈條件下，
左指標從陣列的左邊開始遍歷，遇到偶數就停止，遇到奇數就跳過
右指標從陣列的右邊開始遍歷，遇到奇數就停止，遇到偶數就跳過.

這兩邊遍歷完之后我們會得到 左邊遍歷得到的偶數下標 ，右邊遍歷得到的奇數下標，此時交換這兩個下標的數字

重復以上操作，我們最后得到了一個 奇數在前 偶數在后 (相對位置發生變化) 的 一個陣列序列.

題解代碼

import java.util.* ;

// 這是相對位置發生變化的一種做法
public class Solution {

    public void reOrderArray(int [] array) {
       if(array == null || array.length == 0){
           return;
       }
        
        // 定義一個左右指標
        int left = 0;
        int right = array.length-1;
        
        // 分別從陣列的兩頭開始遍歷
        while(left<=right){
        
// 從左邊開始遍歷 ，遇到偶數停止，遇到奇數跳過

            while(left<right && array[left]%2 ==1){
                left++;
            }
            
// 從右邊開始遍歷 ，遇到奇數停止，遇到偶數跳過

            while(left<right && array[right]%2 == 0){
                right--;
            }
            
     // 此時我們得到了一個左邊是偶數的下標，右邊是奇數的下標
     // 交換奇數 偶數的排列順序
     
     	if(left <= right){
	         int tmp = array[left];
             array[left] = array[right];
             array[right] = tmp;

   	    }
          
            
        }
        
    }
}

相對位置不變

思路

從左向右，每次遇到的，都是最前面的奇數，一定將來要被放在k下標處,

現將當前奇數保存起來

將該奇數之前的內容（偶數序列）,整體向后移動一個位置.

將奇數保存在它將來改在的位置下標（k指向的位置），因為我們是從左往右放的，沒有跨越奇 數，所以一定是相對位置不變的

import java.util.* ;

public class Solution {
    public void reOrderArray(int [] array) {
       if(array == null || array.length == 0){
           return;
       }
        
        int k = 0;
        
        for(int i = 0;i<array.length;i++){
            if(array[i]%2 == 1){
                
                int tmp = array[i];
               for(int j = i-1;j>=k;j--){
                   array[j+1] = array[j];
               }
                       
               array[k++]  = tmp;
            }

        }
        
    }
}

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

題目鏈接：

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?

思路一

思路一：定義map，使用<數字，次數>的映射關系，最后統計每個字符出現的次數

相關代碼

import java.util.*;

public class Solution {

    public int MoreThanHalfNum_Solution(int [] array) {
    
         Map<Integer ,Integer> map = new HashMap<>();
        
        for(int i =0;i<array.length;i++){
            if(map.get(array[i]) == null){
                // 如果這個 arr[i] 沒有在 map 中出現過的話，那么就往 map 中 存上arr[i],且計數為1
                map.put(array[i],1);
            }else{
                // 這種情況是 arr[i] 出現的次數大于1次，出現很多次
                int k = map.get(array[i]);
                // 我們先 用 k 來保存這個arr[i] 在map中之前出現的次數
                map.put(array[i],k+1);
                // arr[i] 存放入 map中，并且次數+1
            }
            
            if(map.get(array[i])>array.length/2){
//                 如果arr[i] 在 map 中出現的次數超過陣列長度的一半，那么直接回傳 arr[i]
                return array[i];
            }
        }
        
        // 因為陣列中可能0出現次數超過長度一半，這里是為了符合邏輯，并不是真正的業務代碼.
        return 0;
        
    }
}

思路二

思路二： 排序，出現次數最多的數字，一定在中間位置，然后檢測中間出現的數字出現的次數是否符合要求

相關代碼

import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
       if(array == null || array.length == 0){
           return 0;
       }
        
        // 我們先將這個陣列進行排序，我們可以 用到幾種排序方法： 直接插入排序、堆排序、冒泡排序、選擇排序等等
        for(int i =0;i<array.length;i++){
           for(int j = 0;j<array.length-1-i;j++){
               if(array[j]>array[j+1]){
                   int tmp = array[j];
                   array[j] = array[j+1];
                   array[j+1] = tmp;
               }
           }    
        }
        
//         如果這個數字出現的次數超過了陣列長度的一半，那么陣列最中間的那個數字一定是 我們想要得到的數字
        int left = 0;
        int right = array.length-1;
        int mid = (left+right)/2;
        int count = 0;
        
        
        for(int i = 0;i<array.length;i++){
            if(array[i] == array[mid]){
                count++;
            }
        }
        
//         如果中間的數字出現的次數大于 陣列長度的一半，那么回傳這個數字，
//         如果沒有，那么回傳0(同樣的，0也只是邏輯上的處理，并不是業務的處理）
        return count>array.length/2 ? array[mid] : 0;
        
    }
}

思路三

思路三：目標條件：目標資料超過陣列長度的一半，那么對陣列，我們同時去掉兩個不同的數字，到最后剩下的一個數就是該數字，如果剩下兩個，那么這兩個也是一樣的，就是結果），在其基礎上把最后剩下的一個數字或者兩個回到原來陣列中，將陣列遍歷一遍統計一下數字出現次數進行最終判斷，

相關代碼

import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
       if(array == null || array.length == 0){
           return 0;
       }
        
     int times = 1;
     int target = array[0];
     
//         下面這個程序很難理解
        
//         每兩個不同的數字 會抵消一次 times
        
//         如果times == 0，那么說明i之前的數字 都不同，再次更換一個 target
        
//         到最后 target 保留的數字很可能是 出現次數超過陣列長度一半的數字
        
        
        for(int i = 1;i<array.length;i++){
            if(times ==0){
          //  如果 times 為0，那么之前不同的抵消完了
                target = array[i];
                times = 1;
            }else if(array[i] == target){
                times++;
            }else{
                times--;
            }
        }
    
     //   如果輸入本身符合條件，那么最后 times 大于0，target 保存的目標就是準目標，但是還需要確認

    int count = 0;
    for(int i = 0;i<array.length;i++){
        if(target == array[i]){
            count++;
        }
    }
    
    return count>array.length/2? target: 0;
    
        
    }
}

??好了，今天的內容就結束了，希望大家多多練習~~

謝謝欣賞！！！