题目描述:
[40]
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
[41]
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
[45]
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
[61]
从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。
考察重点:
第40题 golang中,先排序,后取前k项切片。
第41题使用一个大顶堆一个小顶堆实现中位数求解,元素先进入大顶堆后进入小顶堆,且始终保证小顶堆元素个数小于大顶堆元素个数,最终二者的堆顶平均值或者大顶堆堆顶即是中位数。
第45题先将整个int数组转化为String数组,重写排序规则,按照A+B 第61题顺子表示大小王可以构成任意数字,如“1,4,0,0,5” 可以表示为“1,2,3,4,5”。只需要排序数组并求得0的数量,再判断0的个数是否可以填补顺序数组元素间的差值。
第40题
func getLeastNumbers(arr []int, k int) []int {
sort.Ints(arr)
return arr[:k]
}
第41题
class MedianFinder {
PriorityQueue smallque;
PriorityQueue bigque;
public MedianFinder() {
bigque = new PriorityQueue(new Comparator(){
@Override
public int compare(Integer a1, Integer a2){
return a2 - a1;
}
});
smallque = new PriorityQueue();
}
public void addNum(int num) {
bigque.add(num);
smallque.add(bigque.remove());
if(bigque.size() < smallque.size()){
bigque.add(smallque.remove());
}
}
public double findMedian() {
if(smallque.size() == bigque.size()){
return (bigque.peek() + smallque.peek()) / 2.00000;
}
return bigque.peek();
}
}
第45题
public String minNumber(int[] nums) {
String[] nums2 = new String[nums.length];
for(int i = 0;i < nums.length;i ++){
nums2[i] = String.valueOf(nums[i]);
}
Arrays.sort(nums2, new Comparator(){
@Override
public int compare(String o1, String o2) {
return (o1+o2).compareTo(o2+o1);
}
});
return String.join("", nums2);
}
第61题
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int markZero = 0;
int oldNum = 0;
int i = 0;
for(;i < nums.length;i ++){
if(nums[i] != 0){
break;
}
markZero ++;
}
oldNum = i < nums.length ? nums[i] : 0;
for(i = i + 1;i < nums.length;i ++){
int a = Math.abs(nums[i] - oldNum) - 1;
if(a > markZero || nums[i] == oldNum){
return false;
}else{
markZero = markZero - a;
}
oldNum = nums[i];
}
return true;
}



