JAVA-高频面试题汇总:数组（上）

前言

为了让小伙伴们更好地刷题,我将所有leetcode常考题按照知识点进行了归纳。

高频题汇总:

JAVA-高频面试题汇总:动态规划
JAVA-高频面试题汇总:字符串
JAVA-高频面试题汇总:二叉树(上)
JAVA-高频面试题汇总:二叉树(下)
JAVA-高频面试题汇总:回溯
JAVA-高频面试题汇总:链表

JAVA-高频面试题汇总:数组（上）

接下来还会进行其他模块的总结,有一起在准备暑期实习的JAVA后端的伙伴可以一起交流!
小编微信: Apollo___quan

目录

1. 二维数组中的查找（剑指）
2. 旋转数组的最小数字（剑指）
3. 数值的整数次方（剑指）
4. 调整数组顺序使奇数位于偶数前面（剑指）
5. 顺时针打印矩阵（剑指）
6. 最小的k个数（剑指）
7. 数组中出现次数超过一半的数字（剑指）
8. 把数组排成最小的数（剑指）
9. 丑数(剑指)
10. 数字在排序数组中出现的次数（剑指）

1.二维数组中的查找（剑指）

思路

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length == 0) return false;
        int i = 0;
        int j = matrix[0].length - 1;  //从右上角为起始点，往下增大，往左减小
        while(i <= matrix.length - 1 && j >= 0){ //注意条件是与，当横纵坐标都未超出边界时一直循环
            if(matrix[i][j] > target) j--;
            else if(matrix[i][j] < target) i++;
            else return true;
        }
        return false;
    }
}

2.旋转数组的最小数字（剑指）

思路

方法一（我自己的）：

1.构造一个函数，将数组、起始坐标、终止坐标当作参数传入。注意当起始和终止相等时说明只有一个值，直接返回。

2.二分法，若最左的值>=最右的值，则进行一次二分，比较左半部分与右半部分最小值。反之则返回最左的值。

class Solution {
    public int minArray(int[] numbers) {
       return min(numbers,0,numbers.length-1);
    }
     public int min(int[] arr,int a,int b) {
         if(a==b) return arr[a]; //只剩一个数，直接返回
       if(arr[a]>=arr[b]) {
           int c=(a+b)/2;
           return Math.min(min(arr,a,c),min(arr,c+1,b)); //返回左半和右半的最小值
       }
       else return arr[a]; //arr[a]<arr[b]，返回arr[a]
    }
}

方法二（大佬的）：参考链接

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {  //固定左指针i，不断缩小j
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;  //相等的时候j--，很重要！往中间逼近！
        }
        return numbers[i];
    }
}

3.数值的整数次方（剑指）

思路

class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x; // 判断 nn 二进制最右一位是否为 1，只有当个位为1时才需要相乘，否则不必
            x *= x;  //x^n = x^(a2^0+b2^1+c2^2+..+c2^m) = （x^1）^a*(x^2)^b*(x^4)^c*(x^8)^d+..
            b >>= 1; //n 右移一位（可理解为删除最后一位）
        }
        return res;
    }
}

4.调整数组顺序使奇数位于偶数前面（剑指）

思路

首尾双指针，前指针遇到偶数停，后指针遇到奇数停，交换

class Solution {
    public int[] exchange(int[] nums) {
        if(nums.length <= 1) return nums;
        int i = 0, j = nums.length - 1;
        while(i < j){  //程序进入前判断了i < j，但中途仍然需要判断
            while(((nums[i] & 1) != 0) && (i < j)) i++; //需要注意中途可能会出现i>=j，设置超出数组边界
            while(((nums[j] & 1) != 1) && (i < j)) j--;
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }
}

5.顺时针打印矩阵（剑指）

思路

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break; 
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

6.最小的k个数（剑指）

思路

快排

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
       if(k>input.length||input.length==0||k<=0) return list;
        int l = 0, r = input.length - 1;
        kuaipai(input, l, r, k); 
        int num=0;
        for(int a:input){
            list.add(a);
            if(++num==k) break;
        }
        return list;
    }
    public void kuaipai(int [] input, int l, int r, int k){ //构造了左右指针
        if(l>=r) return;
        int cur = input[l], temp = 0;  //将最左边的树当作哨兵
        int i = l, j = r;
        while(i<j) {  
            while(input[j] >= cur&&i<j) j--; //找到小于cur的数，别忘了添加i<j条件！
            while(input[i] <= cur&&i<j) i++; //找到大于cur的数
            temp = input[j];  //交换input[i]和input[j]，注意最后一次交换时i = j！
            input[j] = input[i];
            input[i] =temp;
        }
        input[i] = cur; //此时input[i] = input[j] =cur，中间值与哨兵交换
        input[l] = temp; //此时temp等于退出while前的input[j]，最左边与中间值交换
        if(k<i+1) kuaipai(input,l,i-1,k); //判断是否继续快排
       if(k>i+1) kuaipai(input,i+1,r,k);
    }

7.数组中出现次数超过一半的数字（剑指）

时间复杂度 O(N)

空间复杂度O(N)

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> hash=new HashMap<>();
        
        for(int i=0;i<array.length;i++){ //遍历数组，key是数组数字，value是出现次数
            if(!hash.containsKey(array[i])){
                hash.put(array[i],1);
            }
            else hash.put(array[i],hash.get(array[i])+1);
        }
        
         for(HashMap.Entry<Integer,Integer> target : hash.entrySet()){ //遍历Map,找到出现次数超过的
           if(2*target.getValue()>array.length)
                  return target.getKey();
        }
        
        return 0;
    }
}

8.把数组排成最小的数（剑指）

思路

时间复杂度 O(NlogN) ： N 为最终返回值的字符数量（ strs 列表的长度 ≤N ）；使用快排或内置函数的平均时间复杂度为 O(Nlog N)，最差为 O(N^2)。
空间复杂度 O(N)： 字符串列表 strs 占用线性大小的额外空间。

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) 
            strs[i] = String.valueOf(nums[i]); //int数组变成string数组
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x)); //String类中对compareTo进行了实现
        StringBuilder res = new StringBuilder();
        for(String s : strs) //从小到大遍历，连接成字符串即可
            res.append(s); 
        return res.toString();
    }
}

9.丑数(剑指)

思路

1.1是第一个丑数

2.丑数 * 质因子 = 丑数

3.要想不漏掉丑数并且使丑数排序，就要求得min（丑数 * 质因子），

例如dp[0] = 1, min（1X2, 1X3, 1X5）,1x2最小，dp[1] = 2, 接着求min（2X2, 1X3, 1X5），dp[2]=3,min（2X2, 2X3, 1X5）,dp[3]=4

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}

10.数字在排序数组中出现的次数（剑指）

思路

二分法，先找左边界lb，再找右边界rb

class Solution {
    public int search(int[] nums, int target) {
            if(nums.length==0) return 0;
            int i = 0; int j = nums.length;
            while(i<j){  //左闭右开
                int mid=i+(j-i)/2;
                if(nums[mid]>=target) j=mid;
                else i=mid+1;
            }
            int rb=i;
             i = 0;  j = nums.length;
            while(i<j){
                int mid=i+(j-i)/2;
                if(nums[mid]>target) j=mid;
                else i=mid+1;
            }
            int lb=j;
            return lb-rb;
    }
}

总结

数组（上）整理完毕，其余类型
JAVA-高频面试题汇总:动态规划
JAVA-高频面试题汇总:字符串
JAVA-高频面试题汇总:二叉树(上)
JAVA-高频面试题汇总:二叉树(下)
JAVA-高频面试题汇总:回溯
JAVA-高频面试题汇总:链表