資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中兩個有序陣列的中位數
假設我們有兩個陣列；這兩個陣列都是有序的。我們需要找到這兩個陣列的中位數。例如，如果陣列是[1,5,8]和[2,3,6,9]，那麼答案是5。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式findMedianSortedArrays，它將接收nums1和nums2陣列作為引數。
如果nums1的長度大於nums2的長度，則：
呼叫函式return findMedianSortedArrays(nums2, nums1)
x := nums1的長度，y := nums2的長度
low := 0, high := x
totalLength := x + y
當low <= high時，執行以下操作：
partitionX := low + (high - low) / 2
partitionY := (totalLength + 1) / 2 - partitionX
當partitionX為0時，maxLeftX = -∞，否則maxLeftX = nums1[partitionX-1]
當partitionX為x時，maxRightX = ∞，否則maxRightX = nums1[partitionX]
當partitionY為0時，maxLeftY = -∞，否則maxLeftY = nums2[partitionY-1]
當partitionY為y時，maxRightY = ∞，否則maxRightY = nums2[partitionY]
如果maxLeftX <= maxRightY 且 maxLeftY <= maxRightX，則：
如果totalLength模2等於0，則：
返回 (maxLeftX 和 maxLeftY 中的最大值 + minRightX 和 minRightY中的最小值) / 2
否則
返回 maxLeftX 和 maxLeftY 中的最大值
否則，如果maxLeftX > maxRightY，則：
high := partitionX - 1
否則 low := partitionX + 1
返回 0
示例 (C++)
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector<int>& nums2) {
if(nums1.size()>nums2.size())
return findMedianSortedArrays(nums2,nums1);
int x = nums1.size();
int y = nums2.size();
int low = 0;
int high = x;
int totalLength = x+y;
while(low<=high){
int partitionX = low + (high - low)/2;
int partitionY = (totalLength + 1)/2 - partitionX;
int maxLeftX = (partitionX ==0?INT_MIN:nums1[partitionX1] );
int minRightX = (partitionX == x?INT_MAX :
nums1[partitionX]);
int maxLeftY = (partitionY ==0?INT_MIN:nums2[partitionY1] );
int minRightY = (partitionY == y?INT_MAX : nums2[partitionY]);
if(maxLeftX<=minRightY && maxLeftY <= minRightX){
if(totalLength% 2 == 0){
return ((double)max(maxLeftX,maxLeftY) + (double)min(minRightX,minRightY))/2;
} else {
return max(maxLeftX, maxLeftY);
}
}
else if(maxLeftX>minRightY)
high = partitionX-1;
else low = partitionX+1;
}
return 0;
}
};
main(){
Solution ob;
vector<int> v1 = {1,5,8}, v2 = {2,3,6,9};
cout << (ob.findMedianSortedArrays(v1, v2));
}輸入
[1,5,8] [2,3,6,9]
輸出
5
370 次瀏覽
