- 计算最接近的数（Java JS Python C）)
(新卷,100分)- 计算最接近的数（Java & JS & Python & C）
题目描述
给定一个数组X和正整数K，请找出使表达式：
X[i] - X[i + 1] - ... - X[i + K - 1]
结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i.
其中，数组中位数：长度为N的数组，按照元素的值大小升序排列后，下标为 N/2 元素的值
输入描述
无
输出描述
无
备注
- 数组X的元素均为正整数
- X的长度n取值范围：2 ≤ n ≤ 1000
- K大于0目小于数组的大小
- i 的取值范围: 0 ≤ i < 1000
- 题目的排序数组X[N]的中位数是X[N/2]
用例
| 输入 | [50,50,2,3],2 |
| 输出 | 1 |
| 说明 |
|
题目解析
本题应该是采用核心代码模式，非ACM模式，因此不需要我们处理输入输出。
下面代码仍然以ACM模式实现，但是会将输入输出处理 和 核心代码 分离。考试时，只需要写出核心代码即可。
本题可以使用滑动窗口解题。
本题其实就是要遍历所有长度为k的滑窗，滑窗内部元素需要按照表达式
X[i] - X[i + 1] - ... - X[i + K - 1]
来求得该滑窗对应得表达式计算结果window。
然后，求解window和数组x中位数mid的差距，差距绝对值越小，则说明二者越接近
结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i.
本题的难点在于滑窗右移时，新、旧滑窗的状态转移。
假设旧滑窗的表达式计算结果为window，那么新滑窗的表达式计算结果应该是：
window - x[i-1] + x[i] * 2 - x[i + k -1]
其中 x[i] * 2 的原因是，新滑窗中x[i]是正的，而旧滑窗中x[i]是负的，为了将-x[i] 变为 +x[i]， 则需要为 -x[i] + x[i] * 2
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on("line", (line) => { const i = line.lastIndexOf(","); const x = line .slice(1, i - 1) .split(",") .map(Number); const k = parseInt(line.slice(i + 1)); console.log(getResult(x, k)); }); function getResult(x, k) { const n = x.length; const midIdx = Math.floor(n / 2); // x数组的中位数 const mid = [...x].sort((a, b) => a - b)[midIdx]; // 初始化滑窗0~k-1, window为滑窗内部元素的表达式计算结果 let window = x[0]; for (let i = 1; i < k; i++) { window -= x[i]; } // window和中位数的差距 let minDiff = Math.abs(mid - window); // window滑窗起始索引 let idx = 0; // 滑窗右移 for (let i = 1; i <= n - k; i++) { // 右移一格后，新滑窗的表达式计算结果 window += -x[i - 1] + 2 * x[i] - x[i + k - 1]; // 新滑窗window值和中位数的差距 const diff = Math.abs(mid - window); // 结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i if (diff <= minDiff) { minDiff = diff; idx = i; } } return idx; }Java算法源码
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String line = sc.nextLine(); int i = line.lastIndexOf(","); int[] x = Arrays.stream(line.substring(1, i - 1).split(",")).mapToInt(Integer::parseInt).toArray(); int k = Integer.parseInt(line.substring(i + 1)); System.out.println(getResult(x, k)); } public static int getResult(int[] x, int k) { int n = x.length; // x数组的中位数 int mid = Arrays.stream(x).sorted().toArray()[n / 2]; // 初始化滑窗0~k-1, window为滑窗内部元素的表达式计算结果 int window = x[0]; for (int i = 1; i < k; i++) { window -= x[i]; } // window和中位数的差距 int minDiff = Math.abs(mid - window); // window滑窗起始索引 int idx = 0; // 滑窗右移 for (int i = 1; i <= n - k; i++) { // 右移一格后，新滑窗的表达式计算结果 window += -x[i - 1] + 2 * x[i] - x[i + k - 1]; // 新滑窗window值和中位数的差距 int diff = Math.abs(mid - window); // 结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i if (diff <= minDiff) { minDiff = diff; idx = i; } } return idx; } }Python算法源码
# 输入获取 tmp = input() i = tmp.rfind(",") x = list(map(int, tmp[1:i-1].split(","))) k = int(tmp[i+1:]) # 核心代码 def getResult(): n = len(x) # x数组的中位数 mid = sorted(x)[n // 2] # 初始化滑窗0~k-1, window为滑窗内部元素的表达式计算结果 window = x[0] for j in range(1, k): window -= x[j] # window和中位数的差距 minDiff = abs(mid - window) # window滑窗起始索引 idx = 0 # 滑窗右移 for i in range(1, n-k+1): # 右移一格后，新滑窗的表达式计算结果 window += -x[i-1] + 2 * x[i] - x[i + k -1] # 新滑窗window值和中位数的差距 diff = abs(mid - window) # 结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i if diff <= minDiff: minDiff = diff idx = i return idx # 算法调用 print(getResult())C算法源码
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_SIZE 1000 int getResult(const int x[], int n, int k); int cmp(const void *a, const void *b) { return (*(int *) a) - (*(int *) b); } int main() { char s[100000]; scanf("%s", s); char *p = strrchr(s, ','); *p = '\0'; int nums[MAX_SIZE]; int nums_size = 0; char *token = strtok(s + 1, ","); while (token != NULL) { nums[nums_size++] = atoi(token); token = strtok(NULL, ","); } int k = atoi(p + 1); printf("%d\n", getResult(nums, nums_size, k)); return 0; } int getResult(const int x[], int n, int k) { int x_cp[n]; for(int i=0; i<n; i++) x_cp[i] = x[i]; // 这里排序的是x_cp数组，不能改变原数组x qsort(x_cp, n, sizeof(int), cmp); // x数组的中位数 int mid = x_cp[n / 2]; // 初始化滑窗0~k-1, window为滑窗内部元素的表达式计算结果 int window = x[0]; for (int i = 1; i < k; i++) { window -= x[i]; } // window和中位数的差距 int minDiff = abs(mid - window); // window滑窗起始索引 int idx = 0; // 滑窗右移 for (int i = 1; i <= n - k; i++) { // 右移一格后，新滑窗的表达式计算结果 window += -x[i - 1] + 2 * x[i] - x[i + k - 1]; // 新滑窗window值和中位数的差距 int diff = abs(mid - window); // 结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i if (diff <= minDiff) { minDiff = diff; idx = i; } } return idx; }
)
