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

╰半夏微凉° 2022-10-27 01:41 300阅读 0赞

## 前言 ##

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

## 高频题汇总: ##

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

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

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

--------------------

## 目录 ##

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

--------------------

##### 1.[二维数组中的查找（剑指）][Link 1] #####

![image-20210111205632596][]

**思路**

![image-20210111205743492][]

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.[旋转数组的最小数字（剑指）][Link 2] #####

![image-20210111211227737][]

**思路**

方法一（我自己的）：

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]
        }
    }

方法二（大佬的）：[参考链接][Link 2]

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.[数值的整数次方（剑指）][Link 3] #####

![image-20210112213112063][]

**思路**

![image-20210206234005397][]

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.[调整数组顺序使奇数位于偶数前面（剑指）][Link 4] #####

![image-20210112220743989][]

**思路**

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

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.顺时针打印矩阵（剑指）][5.] #####

![在这里插入图片描述][20210202224319599.png_pic_center]

**思路**

![image-20210112221644814][]

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个数（剑指）][6._k] #####

![image-20210112223019438][]

**思路**

快排

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.[数组中出现次数超过一半的数字（剑指）][Link 5] #####

![image-20210202180347474][]  
时间复杂度 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.[把数组排成最小的数（剑指）][Link 6] #####

##### ![image-20210202181530761][] #####

**思路**  
![image-20210202183918896][]

时间复杂度 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.[丑数(剑指)][Link 7] #####

![image-20210202184210226][]

**思路**

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.[数字在排序数组中出现的次数（剑指） ][Link 8] #####

![image-20210202223048362][]

**思路**

二分法，先找左边界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- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]  
[JAVA-高频面试题汇总:回溯][JAVA- 4]  
[JAVA-高频面试题汇总:链表][JAVA- 5]

[JAVA-]: https://blog.csdn.net/weixin_44273302/article/details/112000020
[JAVA- 1]: https://blog.csdn.net/weixin_44273302/article/details/112436689
[JAVA- 2]: https://blog.csdn.net/weixin_44273302/article/details/112142969
[JAVA- 3]: https://blog.csdn.net/weixin_44273302/article/details/112200568
[JAVA- 4]: https://blog.csdn.net/weixin_44273302/article/details/113423696
[JAVA- 5]: https://blog.csdn.net/weixin_44273302/article/details/113529501
[Link 1]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[image-20210111205632596]: /images/20221024/9f497d7c878c4b3895e87d62735d9a53.png
[image-20210111205743492]: /images/20221024/5bebcf5cc82f473895dea6ffe5d0c4f1.png
[Link 2]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
[image-20210111211227737]: /images/20221024/10fd97bafa464ca29222d38a036c2bb1.png
[Link 3]: https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/
[image-20210112213112063]: /images/20221024/918a480e869348a8a36467239714d424.png
[image-20210206234005397]: /images/20221024/f8aa0ec2345c49a88b9953dd4396b40b.png
[Link 4]: https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/ti-jie-shou-wei-shuang-zhi-zhen-kuai-man-shuang-zh/
[image-20210112220743989]: /images/20221024/6f30a3cc709e4bc3915bff91d49ab8ce.png
[5.]: https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/
[20210202224319599.png_pic_center]: /images/20221024/280b90324d8d40c394af5d8297e8ba39.png
[image-20210112221644814]: /images/20221024/ea4c4f096d874617aedb7828a603c514.png
[6._k]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/
[image-20210112223019438]: /images/20221024/8e4abdaa5b9e498a8b0ac2c063f6d1fc.png
[Link 5]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[image-20210202180347474]: /images/20221024/d1999dfc95844b2d94e235f4c2e5aa4d.png
[Link 6]: https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/
[image-20210202181530761]: /images/20221024/94a18402b20f4d299eee676bf19d378c.png
[image-20210202183918896]: /images/20221024/0f1df99e396c44d0b86736f43e11d22d.png
[Link 7]: https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/
[image-20210202184210226]: /images/20221024/4efbd71e091a4d728986b9dcc6d29b59.png
[Link 8]: https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
[image-20210202223048362]: /images/20221024/378e168a6aa944a6a7341cc12b776a37.png