遞歸實(shí)現(xiàn)

思路：

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

判斷目標(biāo)值和中心值的大小，若目標(biāo)值小于中心值，則righ變?yōu)閙id - 1，，若大于，則left =mid+1;如等于，則返回。

遞歸實(shí)現(xiàn)：每一步都返回它的上一層。

    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("存在，下標(biāo)是" + index);
        } else {
            System.out.println("不存在");
        }
    }

非遞歸實(shí)現(xiàn)

思路：

• 同上
• 應(yīng)用while循環(huán)實(shí)現(xiàn)
• 每次循環(huán)都要實(shí)現(xiàn)中間值下標(biāo)的改變，注意mid不要定義在循環(huán)外。

 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("存在，下標(biāo)是" + index);
        } else {
            System.out.println("不存在");
        }
    }

二維數(shù)組中查找

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

[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]

給定 target = 7，返回 true。

給定 target = 3，返回 false。

思路：

由題目可知：

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

public class Solution {
    public boolean Find(int target, int [][] array){
        int rows = array.length;  // 獲取行數(shù)
        int cols = array[0].length; // 獲取列數(shù)
        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;
        
    }
}

 時(shí)間復(fù)雜度：O(行數(shù)+列數(shù)) 空間復(fù)雜度O(1)

旋轉(zhuǎn)數(shù)組中的最小數(shù)字

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

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

返回值：1

思路1：

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

時(shí)間復(fù)雜度O(N)

空間復(fù)雜度O(1)

思路2：

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

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;  // 出現(xiàn)錯(cuò)誤
            if(array[mid]>array[last]){ 
            // 如果中間的值比最右端的大，則說(shuō)明中間到左邊的值比最右端的大，
            // 最小值在中間節(jié)點(diǎn)和右端之間產(chǎn)生，反之亦然。
                first = mid+1;  //因?yàn)橹虚g端點(diǎn)的值大于末端的值，所以mid一定不最小的
            }else if(array[mid]<array[last]){
                last = mid;  // 因?yàn)橹虚g的值小于末端的，所以mid可能是最小的
            }else{
               --last;
            }
        }
        return array[first];
    }
}

 出現(xiàn)的錯(cuò)誤：int mid = (last-first)/2+first;將這條語(yǔ)句放在了while循環(huán)外部，導(dǎo)致在循環(huán)內(nèi)部mid無(wú)法進(jìn)行更新。

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

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

調(diào)整數(shù)組使得奇數(shù)在前偶數(shù)在后

題目：輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

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

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

思路：

• 遍歷數(shù)組，先將其中的奇數(shù)找出，放在新數(shù)組的前面，再找出其中的偶數(shù)，將其放在奇數(shù)的后面，要保持原相對(duì)位置不變，則每遍歷出一個(gè)，就存放一個(gè)。
• 因?yàn)槭钦{(diào)整數(shù)組中的數(shù)據(jù)，則在定義一個(gè)新的數(shù)組是，其長(zhǎng)度與原數(shù)組保持一致即可。
• 將數(shù)組遍歷兩遍，先找奇數(shù)，后找偶數(shù)。

import java.util.*;
 
 
public class Solution {
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
     * @param array int整型一維數(shù)組 
     * @return int整型一維數(shù)組
     */
    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];  // 先找出來(lái)奇數(shù)，按順序排在新數(shù)組element中
                size++;  // 假如循環(huán)兩次 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;
    }
}

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

以上就是“幾組時(shí)常遇到的數(shù)組面試題”，你能回答上來(lái)嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動(dòng)力節(jié)點(diǎn)Java官網(wǎng)。