阿星的学习笔记

0%

Java面试问题汇总（一）

发表于 更新于 分类于

前言

本篇文章主要包括如下内容：

  1. 无序数组寻找第K大的值的算法
  2. Java中static关键字的理解
  3. Java中的HashMap
  4. Java中的LinkedHashMap

无序数组寻找第K大的值

问题描述

给定一个数组，寻找其第K大的值，并分析其复杂度

笔者踩的坑

遇到这种问题一定要思考一下，问一下面试官：

  1. 数组是否是数字？
  2. 数组是否有序？
  3. 数组中是否有重复的数字？

笔者没问，回来后后悔不已，毕竟这是笔者第一次面试，把自己的菜展现的一览无余。

我们假设这道题：无序，是数字，无重复。

解决思路

寻找一个标志，遍历数组，将比它小的放在左边，比它大的放在右边（快排），记录比它小的数的个数，如果大于K，则在左边寻找，如果小于K，则在右边寻找。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
	public int find(int[] nums, int k){
		return findKth(nums, k, 0, nums.length);
	}
    public int findKth(int[] nums, int k, int start, int end){
        int p = start;
        int flag = nums[start];
        int count = 0;
        for(int i = start+1; i < end; i++){
            if(nums[i] >= flag) continue;
            else{
                p++;
                exchange(nums, p, i);
                count++;
            }
        }
        exchange(nums,start, p);
        if(count == k -1) return nums[p];
        else if(count > k -1) return findKth(nums, k, start, p);
        else return findKth(nums, k - 1 - count, p+1, end);
    }

    public void exchange(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

}

Java中static关键字的理解

具体可以移步我的博客：浅谈Java类加载机制和static关键字

Java中的HashMap

具体可以移步我的博客：浅谈Java中的HashMap以及红黑树

Java中的LinkedHashMap

具体可以移步我的博客：浅谈Java中LinkedHashMap的实现