資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
