遞歸實現

思路：

定義數組中間的值，mid = (right- left)/2,(要注意左邊的下標要小于右邊下標)

判斷目標值和中心值的大小，若目標值小于中心值，則righ變為mid - 1，，若大于，則left =mid+1;如等于，則返回。

遞歸實現：每一步都返回它的上一層。

    public static int binarySearch1(int[] element, int value, int left, int right) {
        if (left <= right) {
            int mid = (right - left) / 2 + left;
            if (element[mid] > value) {
                right = mid - 1;
                return binarySearch1(element, value, left, right);
            } else if (element[mid] == value) {
                return mid;
            } else {
                left = mid + 1;
                return binarySearch1(element,value,left,right);
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 8, 12};
        int index = binarySearch1(arr, 12, 0, arr.length-1);
        if (index >= 0) {
            System.out.println("存在，下標是" + index);
        } else {
            System.out.println("不存在");
        }
    }

非遞歸實現

思路：

• 同上
• 應用while循環實現
• 每次循環都要實現中間值下標的改變，注意mid不要定義在循環外。

 public static int binarySearch2(int[] element,int value){
        if(element == null){
            return -1;
        }
        int left = 0;
        int right = element.length-1;
        int mid = (right - left)/2 +left;
        while(left <= right){
            if(element[mid] > value){
                right = mid - 1;
                mid = (right - left)/2 +left;
            }else if(element[mid] < value){
                left = mid +1;
                mid = (right - left)/2 +left;
            }else {
                return mid;
            }
        }return -1;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 8, 12};
        int index = binarySearch2(arr, 13);
        if (index >= 0) {
            System.out.println("存在，下標是" + index);
        } else {
            System.out.println("不存在");
        }
    }

二維數組中查找

題目：在一個二維數組中(每個一維數組的長度相同)，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。

[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]

給定 target = 7，返回 true。

給定 target = 3，返回 false。

思路：

由題目可知：

• 二維數組從左到右，從上至下都是依次遞增的;
• 將val = array[row][col]設置在四個邊角(在本題中，我將它設置在了左下角row = rows -1，col = 0，);
• 若val < target,則說明第一列的所有值都是< target(目標值)，所以將 col ++(自增一行);
• 若val > target,則說明最后一行的所有值都是>target(目標值)，所以將 row --(自減一行);
• 循環退出的條件是當行數為0或者列數為0。

public class Solution {
    public boolean Find(int target, int [][] array){
        int rows = array.length;  // 獲取行數
        int cols = array[0].length; // 獲取列數
        if(rows == 0 || cols == 0){
            return false;
        }
        int row = rows - 1;
        int col = 0;
        while(row >= 0 && col <cols){
            if(array[row][col] < target){
                col++;
            }else if(array[row][col] > target){
                row--;
            }else{
                return true;
            }
        }
        return false;
        
    }
}

 時間復雜度：O(行數+列數) 空間復雜度O(1)

旋轉數組中的最小數字

題目:把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。

輸入：[3,4,5,1,2]

返回值：1

思路1：

• 在本題中沒有具體的數值可以進行比較，可以遍歷所有的數組中的值進行比較，選出其中最小的值(不可取)

時間復雜度O(N)

空間復雜度O(1)

思路2：

• 在本題中沒有具體的數值可以進行比較，可以通過端點進行比較。first、mid、last分別作為最左端，中間，最右端，通過mid和first、last中任意一個進行比較，(在本題中，我使用的是最右端)。
• 若中間端大于最右端，則說明左端到中間的值均大于最右端，最小值在中間到右端(不包括中間，因為中間已經大于右端了)
• 若中間端小于右端，則說明最小值可能在最左端到中間(包括中間的值)
• 若中間等于右端，則可能出現111011或者101111的情況，無法判斷在其左邊還是右邊，所以需要遍歷一遍。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;
        }
        int first = 0;
        int last = array.length-1;
        
        while(first<last){
            if(array[first] < array[last]){
                return array[first];
            }
            int mid = (last-first)/2+first;  // 出現錯誤
            if(array[mid]>array[last]){ 
            // 如果中間的值比最右端的大，則說明中間到左邊的值比最右端的大，
            // 最小值在中間節點和右端之間產生，反之亦然。
                first = mid+1;  //因為中間端點的值大于末端的值，所以mid一定不最小的
            }else if(array[mid]<array[last]){
                last = mid;  // 因為中間的值小于末端的，所以mid可能是最小的
            }else{
               --last;
            }
        }
        return array[first];
    }
}

 出現的錯誤：int mid = (last-first)/2+first;將這條語句放在了while循環外部，導致在循環內部mid無法進行更新。

時間復雜度：O(longN) 若是--last的情況，為O(N)

空間復雜度：O(1)(沒有額外開辟空間)

調整數組使得奇數在前偶數在后

題目：輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。

輸入：[1,2,3,4]

返回值：[1,3,2,4]

思路：

• 遍歷數組，先將其中的奇數找出，放在新數組的前面，再找出其中的偶數，將其放在奇數的后面，要保持原相對位置不變，則每遍歷出一個，就存放一個。
• 因為是調整數組中的數據，則在定義一個新的數組是，其長度與原數組保持一致即可。
• 將數組遍歷兩遍，先找奇數，后找偶數。

import java.util.*;
 
 
public class Solution {
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
     * @param array int整型一維數組 
     * @return int整型一維數組
     */
    public int[] reOrderArray (int[] array){
        // write code here
        if(array == null || array.length == 0){
            return array;
        }
        int[] element = new int[array.length];
        int size = 0;
        for(int i = 0;i<array.length;i++){
            if(array[i] % 2 != 0){
                element[size] = array[i];  // 先找出來奇數，按順序排在新數組element中
                size++;  // 假如循環兩次 element[0],element[1],size = 1,2
            }
        }
        for(int i = 0;i<array.length;i++){
            if(array[i]%2 == 0){
                element[size] = array[i]; // element[2];
                size++;
            }
        }
        return element;
    }
}

時間復雜度：O(n)

空間復雜度：O(n)

以上就是“幾組時常遇到的數組面試題”，你能回答上來嗎?如果想要了解更多的Java面試題相關內容，可以關注動力節點Java官網。