第一题 最小的 K 个数
可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字；
Partition 来源于快速排序思想.
观察快速排序是把全部数组排序，当前值需要前k个就行，所以加上对于index与k的判断，只要前k个
package com.lyc.dataautest;
public static int partion2(int[] arr,int start,int end) {
if(arr==null&&start>end) return -1;
int res = arr[start];
while(start<end) {
while(start<end&&arr[end] >= res) {
end--;
}
arr[start] = arr[end];
while(start<end && arr[start]<res) {
start++;
}
arr[end] = arr[start];
}
//初始值给与当前最左边的数字，使得当前数组所有数字包含原数组
arr[start] = res;
return start;
}
public static int[] getLeastNumbers2(int[] input, int k) {
if (input.length == 0 || k <= 0)
return null;
int[] output = new int[k];
int start = 0;
int end = input.length - 1;
int index = partion2(input, start, end);
while(index != k - 1) {
if(index>k-1) {
end = index-1;
index = partion2(input, start, end);
} else {
start = index+1;
index = partion2(input, start, end);
}
}
for (int i = 0; i < k; i++) {
output[i] = input[i];
System.out.print(output[i] + " ");
}
// System.out.println("end print2");
return output;
}
//快速排序
public static void sort_fast(int[] arr,int left,int right) {
if(left>right) return;
int i= partion2(arr,left,right);
sort_fast(arr,left,i-1);
sort_fast(arr,i+1,right);
}
public static void main(String[] args) {
int[] arr = { 4, 5, 1, 6, 2, 7, 3, 8 };
//getLeastNumbers2(arr, 4);
sort_fast(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
第二题 数据流中的中位数
参考 https://blog.csdn.net/u011080472/article/details/51291089
考虑将数据序列从中间开始分为两个部分，左边部分使用大根堆表示，右边部分使用小根堆存储。每遍历一个数据，计数器count增加1，当count是偶数时，将数据插入小根堆；当count是奇数时，将数据插入大根堆。当所有数据遍历插入完成后（时间复杂度为O(logn)O(logn)，如果count最后为偶数，则中位数为大根堆堆顶元素和小根堆堆顶元素和的一半；如果count最后为奇数，则中位数为小根堆堆顶元素。
下午重来
public class Solution {
// 大顶堆，存储左半边元素
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 小顶堆，存储右半边元素，并且右半边元素都大于左半边
private PriorityQueue<Integer> right = new PriorityQueue<>();
// 当前数据流读入的元素个数
private int N = 0;
public void Insert(Integer val) {
// 插入要保证两个堆存于平衡状态
if (N % 2 == 0) {
// N 为偶数的情况下插入到右半边。
// 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
// 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N++;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
}
第三题 字符流中第一个不重复的字符
因为一个字符不会超过8位，所以创建一个大小为256的整形数组，创建一个List，存放只出现一次的字符。insert时先对该字符所在数组位置数量+1，再判断该位置的值是否为1，如果为1，就添加到List中，不为1，则表示该字符已出现不止1次，然后从List中移除，取出时先判断List的size是否为0，不为0直接List.get(0)，就可以得到结果，否则返回‘#’
package com.lyc.dataautest;
import java.util.ArrayList;
public class FirstAppearingOnce {
private int[] chaCnt = new int[256];
private ArrayList<Character> lst = new ArrayList<Character>();
public void insertchar(char ch) {
chaCnt[ch]++;
if (chaCnt[ch] == 1) {
lst.add(ch);
} else {
// 当前的数组是否已经有重复的删除，注意要将Character奉上
lst.remove((Character)ch);
}
}
public char findFist() {
if (lst.size() == 0) {
return '#';
} else {
return lst.get(0);
}
}
public static void main(String[] args) {
StringBuffer stb = new StringBuffer("google");
FirstAppearingOnce fao = new FirstAppearingOnce();
for (int i = 0; i < stb.length() - 1; i++) {
fao.insertchar(stb.charAt(i));
}
for (int i = 0; i < fao.lst.size() - 1; i++) {
System.out.println(fao.lst.get(i));
}
System.out.println(fao.findFist());
}
}
第四题 连续子数组的最大和
首先想到用动态规划算法，设置两个变量，一个currentMax用来记录数组相加之和，一个sumMax用来记录最大的子数组和，一旦currentMax大于sumMax，就更新sumMax使它等于currentMax；初始值都赋予数组的第一个元素的值；
那么问题来了，为什么最大的子数组为0来作为判断，为啥不能是1，哥没想太明白，迷迷糊糊懂……
package com.lyc.dataautest;
public class FindGreatestSumOfSubArray {
public static int findmax(int[] arr) {
if(arr==null) return 0;
int cmax=arr[0];
int res = arr[0];
//注意循环从i=1开始
for(int i=1;i<arr.length;i++) {
if(cmax<0) {
cmax=arr[i];
} else {
cmax+=arr[i];
}
if(cmax>res) {
res = cmax;
}
}
return res;
}
public static void main(String[] args) {
int[] arr={6,-3,-2,7,-15,1,2,2};
int te = findmax(arr);
System.out.println("the res is:"+te);
}
}
网友评论