Leetcode 480. Sliding Window Median
Problem: ? Median is the middle value in an ordered integer list. If the size of the list is even,there is no middle value. So the median is the mean of the two middle value. Examples:
Given an array nums,there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array. For example, Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6 Therefore,return the median sliding window as Note: ? Solution: 这道题思路不难,但写起来有点麻烦,看到这道题,发现和Leetcode 239. Sliding Window Maximum非常相似,但最大值和中值的处理却几乎完全不同,然后考虑用双优先级队列, 但优先级队列的删除操作却非常影响效率,既要删除比较快,又要速度快,map是最好的选择了,一般来说,能用优先级队列的题目用map也能解决。考虑到可能存在重复的数字,所以用left和right两个变量记录small和big两个map的数字和(不能简单的用map.size()),动态添加和删除即可。 Code: ? 1 class Solution { 2 public: 3 void addValue(map<int,int> &small,map<int,int> &big,int &left,int &right,int &value){ 4 if(left == right){ 5 if(small.empty() || value <= small.rbegin()->first){ 6 small[value]++; 7 } 8 else{ 9 big[value]++; 10 small[big.begin()->first]++; 11 big[big.begin()->first]--; 12 if(big[big.begin()->first] == 0) 13 big.erase(big.begin()->first); 14 } 15 left++; 16 } 17 else{ 18 if(value <= small.rbegin()->first){ 19 small[value]++; 20 big[small.rbegin()->first]++; 21 small[small.rbegin()->first]--; 22 if(small[small.rbegin()->first] == 0) 23 small.erase(small.rbegin()->first); 24 } 25 else{ 26 big[value]++; 27 } 28 right++; 29 } 30 } 31 vector<double> medianSlidingWindow(vector<int>& nums,int k) { 32 vector<double> result; 33 bool flag = k%2; 34 int left = 0,right = 0; 35 map<int,int> small,big; 36 for(int i = 0;i != k;++i){ 37 addValue(small,big,left,right,nums[i]); 38 } 39 result.push_back(flag?(small.rbegin()->first):((int64_t)(small.rbegin()->first)+(int64_t)(big.begin()->first))/2.0); 40 for(int i = k;i != nums.size();++i){ 41 int prev = nums[i-k]; 42 if(prev <= small.rbegin()->first){ 43 small[prev]--; 44 if(small[prev] == 0) 45 small.erase(prev); 46 if(!flag){ 47 small[big.begin()->first]++; 48 big[big.begin()->first]--; 49 if(big[big.begin()->first] == 0) 50 big.erase(big.begin()->first); 51 right--; 52 } 53 else 54 left--; 55 } 56 else{ 57 big[prev]--; 58 if(big[prev] == 0) 59 big.erase(prev); 60 if(flag){ 61 big[small.rbegin()->first]++; 62 small[small.rbegin()->first]--; 63 if(small[small.rbegin()->first] == 0) 64 small.erase(small.rbegin()->first); 65 left--; 66 } 67 else 68 right--; 69 } 70 addValue(small,nums[i]); 71 result.push_back(flag?(small.rbegin()->first):((int64_t)(small.rbegin()->first)+(int64_t)(big.begin()->first))/2.0); 72 } 73 return result; 74 } 75 }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- 如何在Windows上配置Ruby以使用指南针进行Sench-touch
- 部署 – 在Windows 8 Pro上加载应用程序
- windows – 区域DNS服务名称
- remote-desktop – 无法远程连接我的Windows 8.1操作系统机
- windows – Directx 11.1中D3DXCOLOR结构的新等价?
- Windows提高_2.2第二部分:用户区同步
- AWS Athena 分析日志
- Windows – 基于现有生产服务器构建Exchange 2010 CAS的最佳
- windows – Powershell删除配置文件脚本 – 错误检查无效
- windows-xp – 可以恢复Active Directory中的密码更改吗?