当前位置:网站首页>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;
}
}
边栏推荐
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 22
- re. Sub() usage
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 24
- 三立期货安全么?期货开户怎么开?目前期货手续费怎么降低?
- Customized version of cacti host template
- IO stream ----- open
- Solaris 10 network services
- R built in data set
- Day01 preliminary packet capture
- SSH principle and public key authentication
猜你喜欢
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 24
Decrypt the advantages of low code and unlock efficient application development
Simple understanding of seesion, cookies, tokens
TCP fast retransmission sack mechanism
Reptile learning 3 (winter vacation learning)
Failed to configure a DataSource: ‘url‘ attribute is not specified... Bug solution
TCP slicing and PSH understanding
How to create a new virtual machine
Elevator dispatching (pairing project) ③
QQ group collection
随机推荐
template<typename MAP, typename LIST, typename First, typename ... Keytypes > recursive call with indefinite parameters - beauty of Pan China
Force buckle 142 Circular linked list II
Snowflake won the 2021 annual database
os. Path built-in module
Here, the DDS tutorial you want | first experience of fastdds - source code compilation & Installation & Testing
Configure SSH key to realize login free
DDS-YYDS
Fundamentals of software testing
Heartbeat报错 attempted replay attack
QQ get group link, QR code
Lvs+kept realizes four layers of load and high availability
Take advantage of the world's sleeping gap to improve and surpass yourself -- get up early
LxC shared directory addition and deletion
Local MySQL forgot the password modification method (Windows)
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 24
Summary of collection: (to be updated)
Number and math classes
LxC shared directory permission configuration
Xiaobing · beauty appraisal
Foreach (system.out:: println) usage