当前位置:网站首页>Leetcode: 408 sliding window median
Leetcode: 408 sliding window median
2022-07-04 11:42:00 【w7486】
The median is the number in the middle of an ordered sequence . If the length of the sequence is even , There is no middle number ; At this point, the median is the average of the two most intermediate numbers .
for example :
[2,3,4], The median is 3
[2,3], The median is (2 + 3) / 2 = 2.5
Give you an array nums, There is a length of k From the left to the right . In the window k Number , Every time the window moves to the right 1 position . Your task is to find out the median number of elements in the new window after each window move , And output an array of them .Example :
give nums = [1,3,-1,-3,5,3,6,7], as well as k = 3.
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 , Returns the median array of the sliding window [1,-1,-1,3,5,6].Tips :
You can assume k Always effective , namely :k Always less than or equal to the number of elements of the input non empty array .
The error with the true value is within 10 ^ -5 The answer within will be regarded as the correct answer .
The first idea is to traverse the array , Take out a window array every time you traverse , Then get the results according to the rules and put them in the result array .
Code:
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
double[] res = new double[nums.length-k+1];
for (int i = 0; i + k <= nums.length; i++) {
Array of sliding windows
double[] arr = new double[k];
for (int j = 0; j < k; j++) {
arr[j] = nums[j+i];
}
// stay arr Get the median in
Arrays.sort(arr);
int mid = k / 2;
res[i] = k % 2 == 0 ? (arr[mid-1] + arr[mid])/2 : arr[mid];
}
return res;
}
}
边栏推荐
- os. Path built-in module
- World document to picture
- Swagger and OpenAPI
- If function in SQL
- How to create a new virtual machine
- Reptile learning 4 winter vacation learning series (1)
- QQ get group settings
- template<typename MAP, typename LIST, typename First, typename ... Keytypes > recursive call with indefinite parameters - beauty of Pan China
- Failed to configure a DataSource: ‘url‘ attribute is not specified... Bug solution
- Post man JSON script version conversion
猜你喜欢
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 8
OSI seven layer reference model
OSI model notes
Summary of Shanghai Jiaotong University postgraduate entrance examination module firewall technology
Post man JSON script version conversion
CSDN documentation specification
Analysis function in SQL
(August 9, 2021) example exercise of air quality index calculation (I)
The latest idea activation cracking tutorial, idea permanent activation code, the strongest in history
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 12
随机推荐
Install freeradius3 in the latest version of openwrt
Attributes and methods in math library
Heartbeat启动后无反应
Games101 Lesson 8 shading 2 Notes
LVS+Keepalived实现四层负载及高可用
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 21
Force buckle 142 Circular linked list II
Elevator dispatching (pairing project) ③
Local MySQL forgot the password modification method (Windows)
[ES6] template string: `string`, a new symbol in es2015
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 19
C language compilation process
03_ Armv8 instruction set introduction load and store instructions
QQ one click cookie acquisition
OSI seven layer reference model
If function in SQL
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 9
Using terminal connection in different modes of virtual machine
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 14
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 8