There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
이게 근데 median이 중간값 아닌가? 예시2에 2.5인게 중앙에 위치한 값이 없어서 2,3을 평균으로 한건가?
[https://ko.wikipedia.org/wiki/%EC%A4%91%EC%95%99%EA%B0%92]
음 맞네
음 근데 O(log(n+m))으로 어떻게 구하지;
음 일단 생각해봤는데
----------
-------------
이렇게 구간이 겹치는 지점을 찾아서 문제를 푸는 횟수를 줄이면 되지 않을까?
구현에 실패 했다.
class Solution {
public:
vector<int> vec;
int med(vector<int>& num1,vector<int>& num2,int st1,int dt1,int st2,int dt2 ,int rank){
int st;
int size1 = num1.size();
int size2 = num2.size();
int median_ind = (size1+size2)/2;
vec.push_back(num1[0]);
vec.push_back(num1[size1-1]);
vec.push_back(num2[0]);
vec.push_back(num2[size2-1]);
sort(vec.begin(), vec.end());
st = vec[1];
if( num1[0] == st || num1[size1-1] == st ){
auto st_iter = upper_bound(num1.begin(),num1.end(),st);
int cnt = st_iter - num1.begin();
}
else if( num2[0] == st || num2[size2 - 1] == st){
auto st_iter = upper_bound(num2.begin(),num2.end(),st);
int cnt = st_iter - num1.begin();
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int ans = med(num1,num2,0,num1.size(),0,num2.size(), (num1.size()+num2.size())/2 );
}
};
음 추가로 구현하긴 했는데 , 안돌아간다.
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
int total;
vector<int> vec;
int med(vector<int>& num1, vector<int>& num2, int st1, int dt1, int st2, int dt2, int rank) {
int st;
int size1 = num1.size();
int size2 = num2.size();
int median_ind = (size1 + size2) / 2;
vec.push_back(num1[0]);
vec.push_back(num1[size1 - 1]);
vec.push_back(num2[0]);
vec.push_back(num2[size2 - 1]);
sort(vec.begin(), vec.end());
st = vec[1];
int cnt,nrank;
if (num2[0] == st || num2[size1 - 1] == st) {
auto st_iter = upper_bound(num1.begin(), num1.end(), st);
cnt = st_iter - num1.begin();
nrank = rank - cnt;
st1 = st1 + cnt ;
if (nrank < 0) {
st1 += rank;
return st1;
}
}
else if (num1[0] == st || num1[size2 - 1] == st) {
auto st_iter = upper_bound(num2.begin(), num2.end(), st);
cnt = st_iter - num1.begin();
nrank = rank - cnt;
st2 = st2 + cnt ;
if (nrank < 0) {
st2 += rank;
return st2;
}
}
return med(num1, num2, st1, dt1, st2, dt2, nrank);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
total = nums1.size() + nums2.size();
int ans = med(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (nums1.size() + nums2.size()) / 2);
return ans;
}
};
고쳤다. 위에서 말한 방법은 시간 복잡도가 최악의 경우 O(n+m)이다.
관점을 좀 바꿨다. 해당 수가 미디언인지 확인하는 편이 빠르다. 한 수가 미디언인지 확인하는 것은 O(logn + logm)이다. 그럼 그 한 수를 어떻게 고를까!? 이걸 바로 이분 탐색으로 골라 본다. 정렬 되있으니까, 즉 이분탐색을 해서 고른 수로 이분탐색을 하는 것이다.! 근데 그럼 logn*logn이 되지 않나;
class Solution {
public:
int is_nth_num(vector<int>& nums1, vector<int>&nums2, int nth,int target){
auto prev1 = lower_bound(nums1.begin(),nums1.end(),target);
auto prev2 = lower_bound(nums2.begin(),nums2.end(),target);
cout << prev1 - nums1.begin()<<"\n";
cout << prev2 - nums2.begin()<<"\n";
int prev = prev1 - nums1.begin() +prev2 - nums2.begin() + 1;
cout << "target, prev, nth : "<< target << " "<< prev<< " "<< nth << "\n";
return prev;
}
int find_nth_num(vector<int>&nums, int nth, vector<int>&nums1,vector<int>&nums2){
int st,dt;
st = 0;
dt = nums.size()-1;
while(st<= dt)
{
int ind = (st+dt)/2;
int target = nums[ind];
int rank = is_nth_num(nums1,nums2,nth,target);
if(rank < nth){
st = ind+1;
}else if ( rank > nth)
{
dt = ind-1;
}
else{
return nums[ind];
}
}
return -1;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total_cnt = nums1.size() + nums2.size();
//2개 찾아야되
int find1,find2;
int ans;
cout << "total_cnt: " << total_cnt<<"\n";
if(total_cnt % 2 == 0){
find2 = total_cnt/2 + 1;
find1 = find1;
int ans1,ans2;
ans1 = find_nth_num(nums1,find1,nums1,nums2);
ans2 = find_nth_num(nums1,find2,nums1,nums2);
if(ans1 == -1)
find_nth_num(nums2,find1,nums1,nums2);
if(ans2 == -1)
find_nth_num(nums2,find2,nums1,nums2);
ans = (ans1+ans2)/2;
}
//1개만 찾으면되.
else{
find1 = total_cnt/2 + 1;
int ans1 = find_nth_num(nums1,find1,nums1,nums2);
if(ans1 == -1)
ans1 = find_nth_num(nums2,find1,nums1,nums2);
ans = ans1;
}
return ans;
}
};
음 이번에는 풀었다. 시간 복잡도가 O(m+n)이라 다시해야된다.
아이디어는 두 배열이 앞에서 부터 작은 것을 선택하도록 했다. 방법은 각 배열에 앞에서 부터 포인터를 두었고, 두 배열을 합해 몇개째 앞에서 부터 카운트 했는지 갯수를 세었다.
구조는 두배열의 총 갯수가 홀수인 경우와 짝수인 경우를 나누었다.
위에 풀이를 다시 보는데, 왜 바보같이 각각이 중간 값인지 확인했지? 이분 탐색에 너무 꽂힌게 아니였을까, 이분탐색하려면 조건이 있는데, 정렬되어 있어야한다는점. 근데 명백히 두개로 나뉘어 있어서 정렬되있는 효과를 보기 어렵다. 그냥 중간값이 몇번째인지 아니까 찾아야 하는 순번이 확실히 결정되서 미디언 찾기가 쉬운데, 대신에 홀짝으로 분리한 이번 구현이 좀 마음에 안들긴 한다, 그리고 배열을 while로 처리한것도 fp에 맞지 않다. fp에 맞는 구현이 궁금하다.
class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
let total_cnt = nums1.count + nums2.count
var ans = 0
if total_cnt % 2 == 0 {
var i = 0
var i1 = 0, i2 = 0
while i <= total_cnt/2 {
i += 1
//print(i)
if i2 == nums2.count || i1 < nums1.count && nums1[i1] <= nums2[i2] {
if i == total_cnt/2 || i == total_cnt/2 + 1{
//print(nums1[i1])
ans += nums1[i1]
}
i1 += 1
}
else if i1 == nums1.count || (i2 < nums2.count && nums1[i1] > nums2[i2]){
if i == total_cnt/2 || i == total_cnt/2 + 1{
//print(nums2[i2])
ans += nums2[i2]
}
i2 += 1
}
}//while
return Double(ans) / 2.0
}
else {
var i = 0
var i1 = 0, i2 = 0
while i <= total_cnt/2 {
i += 1
//print(i)
if i2 == nums2.count || i1 < nums1.count && nums1[i1] <= nums2[i2] {
// print(nums1[i1])
if i == total_cnt/2 + 1 {
// print(nums1[i1])
ans += nums1[i1]
}
i1 += 1
}
else if i1 == nums1.count || (i2 < nums2.count && nums1[i1] > nums2[i2]){
// print(nums2[i2])
if i == total_cnt/2 + 1{
// print(nums2[i2])
ans += nums2[i2]
}
i2 += 1
}
}//while
return Double(ans)
}
return 0
}
}
[https://leetcode.com/problems/median-of-two-sorted-arrays/solution/] 해설은 이해가 안된다... 조만간 되기를 바란다....
다시 접근을 해보자
크게 두가지로 나뉘는거 같다.
1. 찍은 값이 중위값인지 확인해서 찾기
2. 중위값의 위치를 찾기.
음 1,2가 섞일수 있는거 같긴한데...
일단 1로 접근해보자. 한 값을 앞에서 부터 찍고, 그게 중위값인지 확인해보자. 중위값 확인법은, 각 리스트에서 선택한 값보다 앞에 몇개 있는지 확인해서 중간번째가 맞나 보면 된다.
1.확인할 값 정하기 -> 2. 중위값인지 확인하기 즉 2단계가 된다.
젤 쉬운 방법은 앞에서부터(n+m) 그리고 각 리스트안에서 확인 log(n)*log(m)이 된다.
이걸 최적화 해보면, 찾는거 부터 각 리스트에서 log(n)으로 선택하자.
이 과정을 생각해보면 아무리 잘 선택해도 log이고 그거의 번째를 다시 확인한다는게 다시 log이므로 고르고 확인하는건 아닌거 같다. 그렇다면 바로 미디언 번째를 찾는 쪽으로 생각해보자.
그럼 (n+m)/2 째를 이제 k번째라 하자. 두 정렬된 배열에서 k번째가 어딘지 어떻게 찾을것인가....
근데 위치를 찾아간다 했을때 위에 있는지 아래있는지에 따라 결과가 크게 바뀔수 있다.
한 값을 한쪽에서 정하면, 다른 리스트에서 그 값보다 작은게 몇개있는지 알면 양쪽 리스트에서 몇번째인지 알수 있다.
k번째 위치를 찾으려면, 한쪽 리스트에서만 찾아봤자, 다른쪽일수도 있으니까 의미 없는거 같고. 두 리스트에서 같이 조금씩 값을 키워나가서 k번째 위치를 찾는게 맞는듯.
그럼 이제 고민해보자 값을 어떻게 키워 나가며 위치를 찾을까? 두 리스트에서 같이 값을 비슷하게 맞춰가며 키워나가야 된다... 안그러면 찾고 그게 몇번째인지 확인하는 패턴이된다.
내가 n+m으로 푼거랑 비슷하게 찾아야 될거같은데, 한개씩 값을 키워나가기 보다. 두개씩 해도될거같은데?
어떻게 찾아나가야될까...
두 리스트에서 둘다 비슷한 값을 찾아야 정확한 위치를 알수 있다. 정확히는 한 리스트에서 찾은 값 바로 앞뒤값을 다른 리스트에서 찾아야된다.
전략을 세워봤다.
일단 두 리스트 후보들중 중간을 각각 잡는다.
그리고 합한 갯수가 k보다 작거나 같으면 두 포인터가 가리키는 값중 작은값을 앞으로 이동시킨다. 갯수가 많으면 큰값을 뒤로 이동시킨다.
해보자.
class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
var k = []
var size1 = num1.count
var size2 = 0
var point1 = size1 - 1
var point2 = 0
if num1.count + num2.count % 2 == 0{
k += (num1.count + num2.count) / 2
k += (num1.count + num2.count) / 2 + 1
}
else{
k += (num1.count + num2.count) / 2
}
while ( point1 + point2 + 1 == k.0 ){
if point1 + point2 + 1 < k.0 {
}
}
}
}음 구현이 어렵네...
'알고리즘 문제 풀기' 카테고리의 다른 글
| <leet code> Two sum (0) | 2020.03.12 |
|---|---|
| <백준> 17070번 : 파이프 옮기기1 (0) | 2020.03.12 |
| 투포인터 - 백준:2143번 두 배열의 합 (0) | 2020.02.26 |
| 백준 1806번 : 부분합(투포인터) (0) | 2020.02.26 |
| leet code : trapping rain water, 백준 : 히스토그램 6549 (0) | 2020.02.25 |