【华为OD题库-040】计算最接近的数-java

题目

给定一个数组X和正整数K，请找出使表达式X[i]-x[i+1]…-X[i+k-1]，结果最接近于数组中位数的下标i，如果有多个满足条件，请返回最大的i。
其中，数组中位数:长度为N的数组，按照元素的值大小升序排列后，下标为N/2元素的值
补充说明:
1.数组X的元素均为正整数;
2.X的长度n取值范围: 2<= n <= 1000;
3.K大于0且小于数组的大小;
4. i的取值范围:0<=i < 1000;
5.题目的排序数组X[N]的中位数是X[N/2].
示例1
输入:
[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+1]…-X[i+k-1]得出三个数
0 (X[0]-X[1]= 50 -50)，
48(X[1]-X[2]= 50 -2)，
-1(X[2]-X[3]= 2-3)，
其中48最接近50，因此返回下标1

思路

对于任意序列，如：20 5 8 4 3 2 5，k=3
先求中位数，从小到大排序，取中间的数：2 3 4 5 5 8 20，中位数target为5，
初始情况：res=0，diff=20-5-8=7,与target的差值为2。
然后将i右移动，如下：

此时，diff=5-8-4，以j为参照，i=j-k+1; 和上个区间相比：
diff1=20-5-8
diff2=5-8-4
diff2=diff1-nums[j-k]+2*nums[j-k+1]-nums[j]
此时再来计算diff2与target的差值，看他是否更接近target
依次类推，直到j为最后一个元素。
遍历完成后即可得到目标i=j-k+1

题解

package hwod;

import java.util.Arrays;
import java.util.Scanner;

public class CalNearestNum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("],");
        int k = Integer.parseInt(input[1]);
        int[] nums = Arrays.stream(input[0].substring(1).split(",")).mapToInt(Integer::parseInt).toArray();
        System.out.println(calNearestNum(nums, k));
    }

    private static int calNearestNum(int[] nums, int k) {
        //计算中位数
        int[] sortNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortNums);
        int target = sortNums[nums.length / 2];
        int diff = nums[0];
        for (int i = 1; i < k; i++) {
            diff -= nums[i];
        }
        int res = 0;
        int min = Math.abs(diff - target);
        for (int i = k; i <= nums.length - 1; i++) {
            diff = diff - nums[i - k] + 2 * nums[i - k + 1] - nums[i];
            if (Math.abs(diff - target) <= min) {
                res = i - k + 1;
                min = Math.abs(diff - target);

            }
        }

        return res;


    }
}