数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 JavaScript 中查找数组的中位数索引
理解在 JavaScript 中查找数组的中位数索引的复杂性对于寻求揭开数据操作奥秘的开发人员具有重要意义。中位数作为一种集中趋势的统计量度，为数据集的分布和平衡提供了宝贵的见解。利用 JavaScript 的多功能特性，利用算法的力量来确定数组的中位数索引，为分析和从复杂数据集中提取有价值的信息开辟了一个可能性领域。在本文中，我们开始探索在 JavaScript 中确定数组的中位数索引的分步过程，深入研究鲜为人知的技术和函数，这些技术和函数使开发人员能够释放其数据数组中隐藏的宝藏。
问题陈述
创建一个 JavaScript 算法，以查找未排序整数数组中中位数值的索引。对于长度为奇数的数组，中位数是位于中间索引处的元素。对于长度为偶数的数组，中位数最接近两个中心元素的平均值。该算法应有效地处理任何大小的数组，并具有最佳时间复杂度以找到所需的索引。
示例输入 -
Array: [7, 12, 5, 3, 9, 2, 15, 8]
示例输出 -
Index of the element closest to the median: 4
方法
在本文中，我们将看到多种在 JavaScript 中解决上述问题陈述的方法 -
排序方法
快速选择算法
中位数的中位数方法
计数排序算法
方法 1：排序方法
为了在未排序的数组中找到最接近中位数的元素的索引，我们采用排序方法。首先，我们通过将数组长度除以 2 来计算中位数索引。使用名为 calculateMedian 的辅助函数，我们对数组进行排序并根据其长度确定中位数。然后，我们初始化变量 closestIndex 和 minDiff。从索引 1 开始，我们遍历数组，将每个元素与中位数的绝对差与当前最小差进行比较。如果差值更小，我们更新 closestIndex 和 minDiff。最后，我们返回 closestIndex，表示最接近中位数的元素的索引。该方法考虑了绝对差，确保无论元素大小如何都能接近。
示例
给定的代码包含三个函数：findMedianValue、calculateMedian 和 findIndex。findMedianValue 通过使用 calculateMedian 并遍历数组来查找数组中与中位数值最接近的元素。calculateMedian 对数组进行排序并计算中间元素以确定中位数值。findIndex 在数组中查找给定元素的索引。在代码中，定义了一个数组，并使用 findMedianValue 查找中位数元素，然后将其与 findIndex 一起使用以确定其索引。结果打印到控制台。
function findMedianValue(arr) {
const median = calculateMedian(arr);
let medianElement = 0;
let minDiff = Math.abs(arr[0] - median);
for (let i = 1; i < arr.length; i++) {
const diff = Math.abs(arr[i] - median);
if (diff < minDiff) {
minDiff = diff;
medianElement = arr[i];
}
}
return medianElement;
}
function calculateMedian(arr) {
const sortedArr = arr.slice().sort((a, b) => a - b);
const length = sortedArr.length;
if (length % 2 === 0) {
const middle = length / 2;
return (sortedArr[middle - 1] + sortedArr[middle]) / 2;
} else {
const middle = Math.floor(length / 2);
return sortedArr[middle];
}
}
function findIndex(arr,el){
let n=arr.length;
for(let i=0;i<n;i++){
if(arr[i]==el)
return i;
}
return -1;
}
const arr = [1, 7, 3, 6, 5, 6];
const medianElement=findMedianValue(arr);
const medianIndex=findIndex(arr,medianElement);
console.log("Median element index:", medianIndex);
console.log("Median element:", medianElement);
输出
以下是控制台输出 -
Median element index: 3 Median element: 6
方法 2：快速选择算法
为了在 JavaScript 中查找未排序数组中中位数元素的索引，我们可以使用快速选择算法。这涉及定义一个快速选择函数，该函数递归地对数组进行分区，直到找到所需的元素。我们选择一个枢纽元素，根据枢纽重新排列数组，并将枢纽索引与所需索引进行比较。如果它们匹配，我们返回索引。如果枢纽索引更大，我们递归地对左子数组调用快速选择；如果它更小，我们对右子数组调用它。此过程持续进行，直到找到所需的元素。该算法的时间复杂度为 O(n)，使其成为在未排序数组中查找中位数或最接近中位数的元素的有效解决方案。
示例
给定的代码包括查找数组的中位数和确定最接近中位数的元素的索引的函数。"partition" 函数选择一个枢纽元素并重新排列数组。"quickSelect" 递归地查找第 k 个最小元素。"findClosestToMedian" 计算中位数，遍历数组并更新最接近的元素。"findIndex" 遍历数组以查找给定元素的索引。在示例用法中，使用 "findClosestToMedian" 找到最接近中位数的元素，并使用 "findIndex" 找到其索引，然后打印到控制台。
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function quickSelect(arr, low, high, k) {
if (low === high) {
return arr[low];
}
const pivotIndex = partition(arr, low, high);
if (k === pivotIndex) {
return arr[k];
} else if (k < pivotIndex) {
return quickSelect(arr, low, pivotIndex - 1, k);
} else {
return quickSelect(arr, pivotIndex + 1, high, k);
}
}
function findClosestToMedian(arr) {
const n = arr.length;
const medianIndex = Math.floor(n / 2);
const median = quickSelect(arr, 0, n - 1, medianIndex);
let closestValue=0
let closestDiff = Math.abs(arr[0] - median);
for (let i = 1; i < n; i++) {
const diff = Math.abs(arr[i] - median);
if (diff < closestDiff) {
closestDiff = diff;
closestValue=arr[i];
}
}
return closestValue;
}
function findIndex(arr,el){
let n=arr.length;
for(let i=0;i<n;i++){
if(arr[i]==el)
return i;
}
return -1;
}
// Example usage:
const array = [5, 10, 2, 8, 3, 6];
const arrayCopy=JSON.parse(JSON.stringify(array));
const medianElement = findClosestToMedian(array);
const medianIndex=findIndex(arrayCopy,medianElement);
console.log("Median element index:", medianIndex);
console.log("Median element:", medianElement);
输出
以下是控制台输出 -
Median element index: 5 Median element: 6
方法 3：中位数的中位数
为了使用 JavaScript 中的中位数的中位数算法查找未排序数组的中位数或最接近中位数的元素，请按照以下步骤操作。首先，定义主函数 findMedianIndex，并处理数组为空或仅包含一个元素的情况。将中位数索引计算为数组长度除以 2 的地板值。创建一个分区辅助函数，该函数递归地应用中位数的中位数算法以查找枢纽索引。使用枢纽索引将数组划分为两个子数组。根据中位数索引确定要继续搜索的子数组，相应地更新开始或结束索引。最后，对数组调用 findMedianIndex 函数以获取所需的索引。
示例
findMedian 函数使用辅助函数查找数组的中位数元素。swap 函数交换元素，partition 函数围绕枢纽元素对数组进行分区，findMedianOfMedians 函数递归地查找中位数的中位数。findMedian 函数计算中位数索引并返回中位数元素。在示例用法中，findMedian 和 findIndex 函数分别对数组及其副本进行调用，以查找中位数元素及其索引，结果记录到控制台。
function findMedian(arr) {
// Helper function to swap two elements in the array
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Helper function to partition the array around the pivot
function partition(arr, left, right, pivotIndex) {
const pivotValue = arr[pivotIndex];
let partitionIndex = left;
// Move the pivot to the rightmost position
swap(arr, pivotIndex, right);
for (let i = left; i < right; i++) {
if (arr[i] < pivotValue) {
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
// Move the pivot back to its final position
swap(arr, partitionIndex, right);
return partitionIndex;
}
// Helper function to find the median of medians recursively
function findMedianOfMedians(arr, left, right, targetIndex) {
// If the array is small, find the median directly
if (right - left < 5) {
arr = arr.slice(left, right + 1).sort((a, b) => a - b);
return left + Math.floor((right - left) / 2);
}
// Divide the array into groups of size 5 and find the median of each group
for (let i = left; i <= right; i += 5) {
const groupRight = Math.min(i + 4, right);
const medianIndex = findMedianOfMedians(arr, i, groupRight, Math.floor((groupRight - i) / 2));
swap(arr, medianIndex, left + Math.floor((i - left) / 5));
}
// Find the median of medians recursively
const medianOfMediansIndex = findMedianOfMedians(arr, left, left + Math.ceil((right - left) / 5) - 1, Math.floor((right - left) / 10));
// Partition the array around the median of medians
const pivotIndex = partition(arr, left, right, medianOfMediansIndex);
// Compare the pivot index with the target index
if (pivotIndex === targetIndex) {
return pivotIndex;
} else if (targetIndex < pivotIndex) {
return findMedianOfMedians(arr, left, pivotIndex - 1, targetIndex);
} else {
return findMedianOfMedians(arr, pivotIndex + 1, right, targetIndex);
}
}
// Calculate the median index based on the array length
const medianIndex = Math.floor((arr.length - 1) / 2);
// Find the index of the median element using the Median of Median algorithm
const medianElementIndex = findMedianOfMedians(arr, 0, arr.length - 1, medianIndex);
return arr[medianElementIndex];
return medianElementIndex;
}
function findIndex(arr,el){
let n=arr.length;
for(let i=0;i<n;i++){
if(arr[i]==el)
return i;
}
return -1;
}
// Example usage:
const array = [7, 2, 9, 4, 5, 6, 1, 3, 8];
const arrayCopy=JSON.parse(JSON.stringify(array));
const medianElement = findMedian(array);
const medianIndex=findIndex(arrayCopy,medianElement);
console.log("Median element index:", medianIndex);
console.log("Median element:", medianElement);
输出
以下是控制台输出 -
Median element index: 5 Median element: 6
方法 4：计数排序
为了使用 JavaScript 中的计数排序算法查找未排序数组中中位数元素的索引，请按照以下步骤操作：初始化一个计数数组，其长度为最大元素加 1，增加计数数组中每个元素的计数，通过计算累积频率修改计数数组，根据数组长度确定中位数索引，遍历计数数组以查找超过或等于中位数索引的累积和，并将找到的元素的索引作为中位数索引返回。这种方法有效地处理小范围的已知输入值，并且时间复杂度为 O(n+k)，其中 n 是数组长度，k 是值的范围。
示例
提供的代码实现了计数排序以确定数组的中位数。它找到最大值和最小值，初始化 countArray，并根据最小值增加计数。另一个循环通过比较运行计数来查找中位数。索引加上最小值表示中位数。代码还包含一个 findIndex 函数。它通过定义一个示例数组、创建深度副本以及查找中位数及其索引来演示用法。结果打印到控制台。
function findMedian(arr) {
// Counting Sort
const max = Math.max(...arr);
const min = Math.min(...arr);
const countArray = Array(max - min + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
let sum = 0;
for (let i = 0; i < countArray.length; i++) {
sum += countArray[i];
if (sum >= Math.ceil(arr.length / 2)) {
return i + min; // Value at the median index
}
}
}
function findIndex(arr,el){
let n=arr.length ;
for(let i=0;i<n;i++){
if(arr[i]==el)
return i;
}
return -1;
}
// Example usage:
const array = [7, 2, 5, 1, 8, 4];
const arrayCopy=JSON.parse(JSON.stringify(array));
const medianElement = findMedian(array);
const medianIndex=findIndex(arrayCopy,medianElement);
console.log("Median element index:", medianIndex);
console.log("Median element:", medianElement);
输出
以下是控制台输出 -
Median element index: 5 Median element: 4
结论
最后，在 JavaScript 中查找数组的中位数索引的任务揭示了一个复杂但引人入胜的挑战。阐述在于算法和计算的深奥领域，需要一种明智的方法来实现精确性。通过采用很少使用的技巧并利用 JavaScript 的模糊深处，人们可以发现难以捉摸的中位数索引，从而丰富数据操作和分析领域。最后，这项神秘的努力阐明了 JavaScript 的无限可能性，吸引勇敢的程序员拥抱数组探索的未知领域，并揭开中位数索引的谜团。
510 次查看
