网站登录界面 psd,asp网站源码免费版,手机建网站模板,wordpress插件去掉广告计算最接近的数
真题目录: 点击去查看 E B卷 100分题型 题目描述
给定一个数组X和正整数K#xff0c;请找出使表达式#xff1a; X[i] - X[i 1] - … - X[i K - 1] 结果最接近于数组中位数的下标 i #xff0c;如果有多个 i 满足条件#xff0c;请返回最大的 i.
其中请找出使表达式 X[i] - X[i 1] - … - X[i K - 1] 结果最接近于数组中位数的下标 i 如果有多个 i 满足条件请返回最大的 i.
其中数组中位数长度为N的数组按照元素的值大小升序排列后下标为 N/2 元素的值
输入描述
无
输出描述
无
备注
数组X的元素均为正整数X的长度n取值范围2 ≤ n ≤ 1000K大于0目小于数组的大小i 的取值范围: 0 ≤ i 1000题目的排序数组X[N]的中位数是X[N/2]
用例1
输入
[50,50,2,3],2输出
1说明 中位数为50[50,50,2,3]升序排序后变成[2,3,50,50]中位数为下标4/22的元素50计算结果为1X [50,50,2,3] 根据题目计算X[i] - … - 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。 题解
思路
模拟 滑动窗口首先将原数组进行排序获取到中位数。使用滑动窗口迭代获取最接近中位数的值
c
#include cstdint
#include cstdlib
#includeiostream
#includevector
#includestring
#include utility
#include sstream
#includealgorithm
using namespace std;// 通用 split 函数
vectorstring split(const string str, const string delimiter) {vectorstring result;size_t start 0;size_t end str.find(delimiter);while (end ! string::npos) {result.push_back(str.substr(start, end - start));start end delimiter.length();end str.find(delimiter, start);}// 添加最后一个部分result.push_back(str.substr(start));return result;
}int main() {string s;int k;cin s;// 分割字符串获取数组元素以及kvectorstring ans split(s, ],);k stoi(ans[1]);vectorstring numString split(ans[0].substr(1), ,);int n numString.size();vectorint num(n);for (int i 0; i n; i) {num[i] stoi(numString[i]);}// 获取中位数vectorint dp(num);sort(dp.begin(), dp.end());int midNumIndex n / 2;int midValue dp[midNumIndex];int res -1;int diff INT32_MAX;int left n-k, right n - 1;int sum 0;for (int i n - 1; i n - k ; i--) {sum num[i];}// 双指针迭代获取最小值while (left 0) {int tmp num[left] - sum;if (abs(tmp - midValue) diff) {diff abs(tmp- midValue);res left;}sum - num[right--];sum num[left--];}cout res;return 0;
}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 满足条件请返回最大的 iif (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[i1:])# 实现代码
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-k1):# 右移一格后新滑窗的表达式计算结果window -x[i-1] 2 * x[i] - x[i k -1]# 新滑窗window值和中位数的差距diff abs(mid - window)# 结果最接近于数组中位数的下标 i 如果有多个 i 满足条件请返回最大的 iif diff minDiff:minDiff diffidx ireturn idx# 算法调用
print(getResult())JavaScript
/* 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 满足条件请返回最大的 iif (diff minDiff) {minDiff diff;idx i;}}return idx;
}
Go
package mainimport (fmtmathsortstrconvstrings
)func main() {var s stringfmt.Scanln(s)// 分割输入字符串parts : strings.Split(s, ],)numStr : strings.Trim(parts[0], [])k, _ : strconv.Atoi(strings.TrimSpace(parts[1]))// 转换数字字符串为整数数组numStrs : strings.Split(numStr, ,)num : make([]int, len(numStrs))for i, ns : range numStrs {num[i], _ strconv.Atoi(strings.TrimSpace(ns))}n : len(num)// 获取中位数sortedNum : append([]int{}, num...) // 复制一份数组以进行排序sort.Ints(sortedNum)midValue : sortedNum[n/2]res : -1diff : math.MaxInt32left, right : n-k, n-1sum : 0// 初始化 sum 为最后 k-1 个元素的总和for i : n - 1; i n-k; i-- {sum num[i]}// 滑动窗口查找最接近中位数的起始位置for left 0 {tmp : num[left] - sumif abs(tmp-midValue) diff {diff abs(tmp - midValue)res left}sum - num[right]right--sum num[left]left--}fmt.Println(res)
}// 计算绝对值的辅助函数
func abs(x int) int {if x 0 {return -x}return x
}
