计算最接近的数

题目描述

给定一个数组 X 和 正整数 K，请找出使表达式：

X[i] - X[i+1] - ...... - X[i + K - 1]

结果最接近于数组中位数的下标 `i` , 如果有多个 `i` 满足条件，请返回最大的 `i`

其中，数组中位数：长度为 N 的数组，按照元素的值大小升序排列后，下标为 N/2 元素的值

备注

1. 数组X的元素均为正整数
2. X的长度 n 的取值范围：
3. 
4. 
5. 题目的排序数组的中位数是

用例

--输入
[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);
    }

}