几组时常遇到的数组面试题

递归实现

思路：

定义数组中间的值，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官网。