数据流中的中位数
描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
题目意思就是当遍历到第一个数5的时候 因为此时为一个数为奇数 所有返回中间的一个
遍历到2时候 此时遍历了2个数字 因为是偶数 排序 返回俩个数的中位数
遍历3时候 此时遍历了3 个数字 因为是奇数 排序{2,3,5} 返回中位数 3
遍历4时候 此时遍历了4 个数字 为偶数 排序{2,3,4,5} 返回 (3+4)/2 ..........
题目分析:
思路一:暴力
import java.util.*;public class Solution {ArrayList<Integer> list = new ArrayList<>();int count = 0;public void Insert(Integer num) {list.add(num);count++;}public Double GetMedian() {Collections.sort(list);return count%2==1 ?(double)list.get(count/2):(double)(list.get(count/2)+list.get((count/2-1)))/2;}
}
思路二:堆排序
我们来看看中位数的特征,它是数组中间个数字或者两个数字的均值,它是数组较小的一半元素中最大的一个,同时也是数组较大的一半元素中最小的一个。那我们只要每次维护最小的一半元素和最大的一半元素,并能快速得到它们的最大值和最小值,那不就可以了嘛。这时候就可以想到了堆排序的优先队列。
使用一个大根堆min维护较小一半元素 堆顶为较小元素的最大值
使用一个小跟堆max维护较大一半元素 堆顶为较大元素的最小值如果一个数组为奇数 设置大根堆个数比小根堆多上一个 返回的时候直接返回大根堆的堆顶元素即可
如果为偶数 设置相同数量的大小根堆 返回的时候取平均在大小根堆的堆顶元素
每次输入的数据流先进入大顶堆min排序,然后将大顶堆的堆顶弹入小顶堆max中,完成整个的排序
但是因为大顶堆min的数据不可能会比小顶堆max少一个,因此需要再比较二者的长度,若是小顶堆长度大于大顶堆,需要从小顶堆中弹出堆顶到大顶堆中进行平衡
import java.util.*;public class Solution {//大根堆PriorityQueue<Integer> min = new PriorityQueue<>((o1, o2)->o2 - o1);//小根堆PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2)->o1 - o2);public void Insert(Integer num) {min.offer(num);max.offer(min.poll());if (max.size() > min.size()) {min.offer(max.poll());}}public Double GetMedian() {//奇数个if (min.size() > max.size()) {return (double)min.peek();} else {return (double)(max.peek() + min.peek()) / 2;}}
}
逆波兰表达式求值
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+
(a+b)*c-(a+b)/e的后缀表达式为:
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
题目分析
逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作:
如果遇到操作数,则将操作数入栈;
如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。
整个逆波兰表达式遍历完毕之后,栈内只有一个元素,该元素即为逆波兰表达式的值。
class Solution {public int evalRPN(String[] tokens) {Stack<Integer> s = new Stack<>();for(int i = 0;i < tokens.length; i++) {String str = tokens[i];if(isNumber(str)) {s.push(Integer.parseInt(str));} else {int num1 =s.pop();int num2 =s.pop();switch(str) {case "+" :s.push(num2+num1);break;case "-" :s.push(num2-num1);break;case "*" :s.push(num2*num1);break;case "/" :s.push(num2/num1);break;default : }}}return s.pop(); }public boolean isNumber(String str) {return !(str.equals("+") || str.equals("-")||str.equals("*")||str.equals("/")) ;}
}
最长连续序列
给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
题目分析:
细节 :此题目只需要它连续的个数,即使有重复的数字也没关系,跟我们以前求的最长连续的数组有所差异
所以到了 nums[i+1] 比 nums[i] 大 1 或者 相等的情况下 ,继续判断 只有相差为1的情况下才进行count++,否则就不动
其他情况 就重新重置为1
class Solution {public int longestConsecutive(int[] nums) {if(nums.length == 0) {return 0;}Arrays.sort(nums);int count = 1,ret = 1;for(int i = 1;i<nums.length;i++) {if(nums[i] - nums[i-1] == 0 || nums[i] -nums[i-1] == 1) {if(nums[i] -nums[i-1] == 0) {count--;}count++;} else {count = 1;}ret = Math.max(ret,count); }return ret;}
}
解法二:哈希表
将所有的数字先丢进hash表中
我们只要知道什么时候数字为起点?
答案就是这个数的前一个数不存在于数组中
我们就要遍历这个连续序列,什么时候是终点呢?
答案是当前数x的后一个数
x+1
不存在于数组中
class Solution {public int longestConsecutive(int[] nums) {HashSet<Integer> hash = new HashSet<>();for(int i : nums) {hash.add(i);}int ret = 0,count;for(int x : hash) {if(!hash.contains(x-1)) {//此时为起点count = 0;while(hash.contains(x)) {x++;count++;}ret = Math.max(count,ret);}}return ret;}
}
字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
题目分析:
创建一个hash表 Key为String ,Value 为String[]
1.进行遍历整个数组
拿到其中的数组元素 先将它排序 可以获取到最原始Key
2.如果发现hash表中存在Key,可以直接在它的Value后面添加
创建一个String[]即可 然后在它的Value后面添加
3.最后返回hash表上的value即可
class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String,List<String>> hash = new HashMap<>();for(String str : strs) {char[] ch = str.toCharArray();Arrays.sort(ch);String s = new String(ch);if(!hash.containsKey(s)) {hash.put(s,new ArrayList<>());}hash.get(s).add(str);}return new ArrayList<>(hash.values());}
}
1122-23俩日
结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力!