题目描述
给定一个数组 X
和 正整数 K
,请找出使表达式:
X[i] - X[i+1] - ...... - X[i + K - 1]
结果最接近于数组中位数的下标 `i` , 如果有多个 `i` 满足条件,请返回最大的 `i`
其中,数组中位数:长度为 N
的数组,按照元素的值大小升序排列后,下标为 N/2
元素的值
备注
- 数组
X
的元素均为正整数 X
的长度n
的取值范围:- 题目的排序数组
的中位数是
用例
--输入
[50,50,2,3],2
--输出
1
--说明
1.
--中位数为50: [50,50,2,3]升序排序后变成 [2,3,50,50]
--中位数为下标-> 4/2=2 的元素 50
2.计算结果为1: X [50.50,2,3] 根据题目计算X[i] - ... - X[i + k- 1] 得出三个数
0 (X[O] - X[1] = 50 - 50)
48 (X[1] - X[2] = 50 - 2)
-1 (X[2] - X[3] = 2 - 3)
其中48最接近50,因此返回下标1。
show code
import java.util.Arrays;
import java.util.Scanner;
/**
* desc :
* <p>
* create time : 2023/9/9 16:41
*/
public class CalculateTheClosestNumber {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()) {
String line = in.nextLine();
String[] split = line.split("]");
String[] split1 = split[0].replace("[", "").split(",");
int[] X = new int[split1.length];
for (int i = 0; i < split1.length; i++) {
X[i] = Integer.parseInt(split1[i]);
}
int k = Integer.parseInt(split[1].replace(",", ""));
//calculateTheClosestNumber(X, k);
practice(X, k);
}
}
private static void practice(int[] X, int k) {
int n = X.length;
// 求数组的中位数.
int mid = Arrays.stream(X).sorted().toArray()[n/2];
// 滑动窗口
int window = X[0];
for (int i = 1; i < k; i++) {
window -= X[i];
}
// 和中位数的差距.
int min_diff = Math.abs(mid - window);
int idx = 0;
// 滑动窗口右移
for (int i = 1; i <= n - k; i++) {
// 右移动一格
window += 2 * X[i] - X[i - 1] - X[i + k - 1];
int diff = Math.abs(mid - window);
if(diff <= min_diff) {
min_diff = diff;
idx = i;
}
}
System.out.println(idx);
}
}
标签:数组,int,50,中位数,--,split,计算,接近
From: https://blog.51cto.com/u_16079703/7504078