資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使陣列中位數等於 K 的最小運算元
問題“使陣列中位數等於 K 的最小運算元”用於調整整數陣列的元素，使其中位數等於給定值 k。在一次操作中，您可以將任何元素增加或減少 1。
問題陳述
目標是找到使陣列中位數等於 K 的最小運算元。陣列的中位數是在陣列按非遞減順序排序時位於中間的元素。如果存在兩個中間元素，則較大的一個被認為是中位數。
示例場景 1
Input: nums = [7, 1, 4], k = 5
Output: 1
排序後的陣列 = [1, 4, 7]，中位數 = 4，操作 = 將 4 增加到 5（1 次操作），總運算元 = 1。
示例場景 2
Input: nums = [10, 2, 8, 6, 4], k = 6
Output: 0
排序後的陣列 = [2, 4, 6, 8, 10]，中位數 = 6。不需要操作，因為中位數已經是 6。
示例場景 3
Input: nums = [20, 5, 15, 10, 25], k = 18
Output: 3
排序後的陣列 = [5, 10, 15, 20, 25]，中位數 = 15，操作 = 將 15 增加到 18（15(+1+1+1): 3 次操作），總運算元 = 3。
示例場景 4
Input: nums = [12, 3, 2, 9, 5, 11 ], k = 9
Output: 0
排序後的陣列 = [2, 3, 5, 9, 11, 12]，中位數 = 9，不需要執行操作，因為它已經等於中位數。此處 5, 9 是中位數，因為 9 最大，它是中位數且等於 k。
時間複雜度
對 (n) 個元素的陣列進行排序的時間複雜度為 O(n log n)，計算中位數需要遍歷陣列，這需要 O(n) 的時間，其中 n 是運算元。
為了用各種程式語言解決這個問題，可以使用以下方法。
- 排序和二分查詢
- 雙指標技術
排序和二分查詢
示例
以下方法對陣列進行排序以查詢中位數，並使用二分查詢來查詢使中位數等於 k 所需運算元最少的最佳值。
#include <iostream>
#include <vector>
#include <algorithm>
int minOperationsToMedian(std::vector<int>& nums, int K) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
int medianIndex = n / 2;
int operations = 0;
if (nums[medianIndex] != K) {
operations = std::abs(nums[medianIndex] - K);
}
return operations;
}
int main() {
std::vector<int> nums = {20, 5, 15, 10, 25};
int K = 18;
std::cout << "Minimum operations = " << minOperationsToMedian(nums, K) << std::endl;
return 0;
}
輸出
Minimum operations = 3
import java.util.Arrays;
public class MinOperationsToMedian {
public static int minOperationsToMedian(int[] nums, int K) {
Arrays.sort(nums);
int n = nums.length;
int medianIndex = n / 2;
int operations = 0;
if (nums[medianIndex] != K) {
operations = Math.abs(nums[medianIndex] - K);
}
return operations;
}
public static void main(String[] args) {
int[] nums = {20, 5, 15, 10, 25};
int K = 18;
System.out.println("Minimum operations = " + minOperationsToMedian(nums, K));
}
}
輸出
Minimum operations = 3
def min_operations_to_median(nums, K):
nums.sort()
n = len(nums)
median_index = n // 2
operations = 0
if nums[median_index] != K:
operations = abs(nums[median_index] - K)
return operations
nums = [20, 5, 15, 10, 25]
K = 18
print("Minimum operations = ", min_operations_to_median(nums, K))
輸出
Minimum operations = 3
package main
import (
"fmt"
"math"
"sort"
)
func minOperationsToMedian(nums []int, K int) int {
sort.Ints(nums)
n := len(nums)
medianIndex := n / 2
operations := 0
if nums[medianIndex] != K {
operations = int(math.Abs(float64(nums[medianIndex] - K)))
}
return operations
}
func main() {
nums := []int{20, 5, 15, 10, 25}
K := 18
fmt.Println("Minimum operations =", minOperationsToMedian(nums, K))
}
輸出
Minimum operations = 3
雙指標技術
示例
在這種技術中，我們使用兩個指標來識別排序陣列中的中位數位置，並調整中位數兩側的元素以使中位數等於 k。
#include <bits/stdc++.h>
using namespace std;
int minOperationsToMakeMedianK(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int operations = 0;
for (int i = 0; i < n / 2; ++i) {
operations += max(0, nums[i] - k);
}
for (int i = n / 2; i < n; ++i) {
operations += max(0, k - nums[i]);
}
return operations;
}
int main() {
vector<int> nums = {20, 5, 15, 10, 25};
int k = 18;
cout <<"Minimum operations = " << minOperationsToMakeMedianK(nums, k) << endl;
return 0;
}
輸出
Minimum operations = 3
import java.util.Arrays;
public class Main {
public static int minOperationsToMakeMedianK(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int operations = 0;
for (int i = 0; i < n / 2; ++i) {
operations += Math.max(0, nums[i] - k);
}
for (int i = n / 2; i < n; ++i) {
operations += Math.max(0, k - nums[i]);
}
return operations;
}
public static void main(String[] args) {
int[] nums = {20, 5, 15, 10, 25};
int k = 18;
System.out.println("Minimum operations = " + minOperationsToMakeMedianK(nums, k));
}
}
輸出
Minimum operations = 3
import math
def min_operations_to_make_median_k(nums, k):
nums.sort()
n = len(nums)
operations = 0
for i in range(n // 2):
operations += max(0, nums[i] - k)
for i in range(n // 2, n):
operations += max(0, k - nums[i])
return operations
nums = [20, 5, 15, 10, 25]
k = 18
print(f"Minimum operations = {min_operations_to_make_median_k(nums, k)}")
輸出
Minimum operations = 3
package main
import (
"fmt"
"sort"
)
func minOperationsToMakeMedianK(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
operations := 0
for i := 0; i < n/2; i++ {
operations += max(0, nums[i]-k)
}
for i := n / 2; i < n; i++ {
operations += max(0, k-nums[i])
}
return operations
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
nums := []int{20, 5, 15, 10, 25}
k := 18
fmt.Println("Minimum operations =", minOperationsToMakeMedianK(nums, k))
}
輸出
Minimum operations = 3
更新於：2024年7月23日
瀏覽量：55
廣告