华为OD机试 C++【最接近的数】

爱被打了一巴掌 2024-03-08 08:15 68阅读 0赞

### 题目 ###

任务:  
假设你有一个正整数数组X和一个整数K。请计算下式的结果：

X\[i\] - X\[i + 1\] - … - X\[i + K - 1\]

你的目标是找到使这个结果与数组的中位数最为接近的i值。如果有多个相同的结果，请返回最大的i。

额外信息：

数组的中位数是什么？当你把数组从小到大排序后，中间那个数字就是中位数。  
你可以假设数组X里的元素都是正整数。  
数组X的长度n限制为：2 ≤ n ≤ 1000。  
K的值肯定小于数组的大小。  
i的范围是：0 ≤ i < 1000。  
例子:  
输入: \[50,50,2,3\], 2  
输出: 1

为什么？首先，这个数组排序后为\[2,3,50,50\]，中位数是50。接着，我们按照上面的公式计算，找到差值与50最接近的是X\[1\] - X\[2\]，所以返回1。

### 代码 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <climits>
    
    using namespace std;  
    
    // 计算从给定位置开始的子数组的差值
    int calculateDifferenceFromStart(const vector<int>& arr, int startPos, int k) {
        
        int result = arr[startPos];
        for (int i = 1; i < k; ++i) {
        
            result -= arr[startPos + i];
        }
        return result;
    }
    
    // 寻找最接近中位数的子数组的起始位置
    int findClosestToMedianStart(const vector<int>& nums, int k) {
        
        // 计算中位数
        vector<int> sortedNums(nums);
        sort(sortedNums.begin(), sortedNums.end());
        int median = sortedNums[nums.size() / 2];
    
        int smallestDiff = INT_MAX;
        int bestStartPos = -1;
    
        for (int i = 0; i <= nums.size() - k; ++i) {
        
            int currentDiff = abs(median - calculateDifferenceFromStart(nums, i, k));
            if (currentDiff < smallestDiff || (currentDiff == smallestDiff && i > bestStartPos)) {
        
                smallestDiff = currentDiff;
                bestStartPos = i;
            }
        }
    
        return bestStartPos;
    }
    
    int main() {
        
        //题目给出的测试数据
        vector<int> inputNumbers = {
         50, 50, 2, 3 };
        int subArrayLength = 2;
        cout << findClosestToMedianStart(inputNumbers, subArrayLength) << endl;  // 输出：1
        return 0;
    }