[Question]
How to design a queue A, in addition to insert(), delete(), also has a function min() which returns the minimum element? Can you do all functions in O(1) time?
[Analysis]
Need an additional queue X to record each potential minimum elements along the way. Those are elements in queue A that are smaller than the last incoming element (the end of the queue). When adding a new element, queue X will need to remove the elements that are larger than the new element.
The time complexity for min(), insert() and delete() is amortized O(1).
[Solution]
import java.util.*;
public class QueueWithWeights implements TestCaseRunner{
// -- interface of weights
public interface WeightedObject {
public int getWeight();
}
// -- class WeightedString is for testing purpose;
public class WeightedString implements WeightedObject {
String str;
int wgt;
WeightedString (String a, int w) {
str = a;
wgt = w;
}
public int getWeight() {
return wgt;
}
}
// -- members of the queue;
List<WeightedObject> oList;
List<Integer> wList;
// -- constructor;
QueueWithWeights() {
oList = new ArrayList<WeightedObject> ();
wList = new ArrayList<Integer>();
}
public void insert(WeightedObject a) {
oList.add(a);
int i = wList.size()-1;
while (i>=0 && a.getWeight()<wList.get(i)) {
wList.remove(i--); //amortized O(1);
}
wList.add(a.getWeight());
}
public WeightedObject delete() {
if (oList.size()>0) {
if (oList.get(0).getWeight() == wList.get(0)) {
wList.remove(0);
}
return oList.remove(0);
}
return null;
}
public int min() {
if (oList.isEmpty()) return Integer.MIN_VALUE;
return wList.get(0);
}
public void runTestCases() {
int[] w = {3, 4, 5, 8, 5, 3, 2, 1, 2, 3, 9 , 10, 9, 8, 7, 6, 5, 4, 3, 6, 7};
QueueWithWeights que = new QueueWithWeights();
int j = 3;
for (int i: w) {
WeightedString s = new WeightedString(String.valueOf(i), i);
que.insert(s);
System.out.println("inserted " + i);
System.out.println("min " + que.min());
j--;
if (j==0) {
System.out.println("delete "+que.delete().getWeight());
System.out.println("min " + que.min());
System.out.println("delete "+que.delete().getWeight());
System.out.println("min " + que.min());
j=3;
}
}
}
}
Tuesday, April 24, 2012
Clone a Directed Acyclic Graph (DAG)
[Question]
Write a function to copy a Directed Acyclic Graph (DAG) -- http://en.wikipedia.org/wiki/Directed_acyclic_graph.
class Node {
int value;
vector<Node *> neighbors;
};
Node *copyGraph(Node *root) {
// add code here
}
[Analysis]
Using DFS (Depth First Search) and a recursive function. Note the copy of next node could be created before the DFS reaches it, so a hashmap is needed to record the nodes that have been created.
In actual DAG, there may be many vertices which have no incoming edges. So there could be many starting vertices for DFS. This can be justified by using an extra node which reaches all starting vertices in the DAG. Using this extra node as root, the clone function will work the same.
The time complexity is O(n+m), n is number of vertices, m is number of edges.
[Solution]
// In Java
public class DAGraph {
public class Node {
int value;
List<Node> list;
}
public Node cloneDAGraph (Node root) {
return cloneDAGraph( root, new HashMap<Node,Node>() );
}
public Node cloneDAGraph (Node root, Map<Node, Node> map) {
if (root == null) return null;
if (map.containsKey(root)) return map.get(root);
Node newNode = new Node();
newNode.value = root.value;
newNode.list = new ArrayList<Node>();
map.put(root, newNode);
for(Node n: root.list) {
newNode.list.add(cloneDAGraph(n, map));
}
return newNode;
}
}
Write a function to copy a Directed Acyclic Graph (DAG) -- http://en.wikipedia.org/wiki/Directed_acyclic_graph.
class Node {
int value;
vector<Node *> neighbors;
};
Node *copyGraph(Node *root) {
// add code here
}
[Analysis]
Using DFS (Depth First Search) and a recursive function. Note the copy of next node could be created before the DFS reaches it, so a hashmap is needed to record the nodes that have been created.
In actual DAG, there may be many vertices which have no incoming edges. So there could be many starting vertices for DFS. This can be justified by using an extra node which reaches all starting vertices in the DAG. Using this extra node as root, the clone function will work the same.
The time complexity is O(n+m), n is number of vertices, m is number of edges.
[Solution]
// In Java
public class DAGraph {
public class Node {
int value;
List<Node> list;
}
public Node cloneDAGraph (Node root) {
return cloneDAGraph( root, new HashMap<Node,Node>() );
}
public Node cloneDAGraph (Node root, Map<Node, Node> map) {
if (root == null) return null;
if (map.containsKey(root)) return map.get(root);
Node newNode = new Node();
newNode.value = root.value;
newNode.list = new ArrayList<Node>();
map.put(root, newNode);
for(Node n: root.list) {
newNode.list.add(cloneDAGraph(n, map));
}
return newNode;
}
}
Monday, April 23, 2012
Linked List Rotation
[Question]
[Analysis]
Just need to be careful that the k could be larger than the length of the linked list.
[Solution]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head==null) return null;
ListNode p = head;
int count=0;
while (p.next!=null) {
count++;
p=p.next;
}
count++;
p.next = head;
n = n % count;
p=head;
while (n+1<count) {
n++;
p=p.next;
}
head = p.next;
p.next = null;
return head;
}
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given
return
Given
1->2->3->4->5->NULL and k = 2,return
4->5->1->2->3->NULL.[Analysis]
Just need to be careful that the k could be larger than the length of the linked list.
[Solution]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head==null) return null;
ListNode p = head;
int count=0;
while (p.next!=null) {
count++;
p=p.next;
}
count++;
p.next = head;
n = n % count;
p=head;
while (n+1<count) {
n++;
p=p.next;
}
head = p.next;
p.next = null;
return head;
}
}
Sunday, April 22, 2012
Edit Distance
[Question]
//--- C++ ---
class Solution {
public:
int minDistance(string word1, string word2) {
if (word1.size()==0) return word2.size();
if (word2.size()==0) return word1.size();
vector<vector<int>> E (word2.size()+1, vector<int>(word1.size()+1, 0));
for (int i=0; i<word1.size()+1; i++)
E[0][i] = i;
for (int j=0; j<word2.size()+1; j++)
E[j][0] = j;
for (int i=1; i<word2.size()+1; i++) {
for (int j=1; j<word1.size()+1; j++) { //note: j needs to start from index 1.
int tmp = min (E[i-1][j]+1, E[i][j-1]+1);
mtx[i][j] = min( tmp, (word2[i-1]==word1[j-1])?E[i-1][j-1] : E[i-1][j-1]+1 );
}
}
return E.back().back();
}
};
//--- Java ---
public class Solution {
public int minDistance(String word1, String word2) {
if (word1.length()==0) return word2.length();
if (word2.length()==0) return word1.length();
int [] dist = new int[word1.length()+1];
for (int i=0; i<dist.length; i++)
dist[i] = i;
for (int j=0; j<word2.length(); j++) {
int d0= dist[0];
int d1= 0;
dist[0] = j+1;
for (int i=1; i<dist.length; i++) {
d1 = dist[i];
if (word2.charAt(j) == word1.charAt(i-1)) {
dist[i] = d0;
} else {
dist[i] = Math.min(Math.min(d0+1, d1+1), dist[i-1]+1);
}
d0=d1;
}
}
return dist[dist.length-1];
}
}
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
b) Delete a character
c) Replace a character
[Analysis]
The problem is a classic example of Dynamic Programming. It is called Levenshtein Distance. There is an excellent analysis in wiki: http://en.wikipedia.org/wiki/Levenshtein_distance.
Suppose word1 is A[0]...A[m] and word2 is B[0]...B[n]. The Edit Distance E[m,n] can be derived as follow:
E[i, j] = min (E[i-1,j]+1, E[i,j-1]+1, E[i-1, j-1]+1) if A[i]!=B[j];
E[i, j] = min (E[i-1,j]+1, E[i,j-1]+1, E[i-1, j-1]) if A[i]==B[j];
When A and B are both empty, the Edit Distance is 0. To simplify the coding, we can add one extra column and row in E. E takes (m+1) x (n+1) space; this can be simplified to linear (m+1).
[Solution]Suppose word1 is A[0]...A[m] and word2 is B[0]...B[n]. The Edit Distance E[m,n] can be derived as follow:
E[i, j] = min (E[i-1,j]+1, E[i,j-1]+1, E[i-1, j-1]+1) if A[i]!=B[j];
E[i, j] = min (E[i-1,j]+1, E[i,j-1]+1, E[i-1, j-1]) if A[i]==B[j];
When A and B are both empty, the Edit Distance is 0. To simplify the coding, we can add one extra column and row in E. E takes (m+1) x (n+1) space; this can be simplified to linear (m+1).
//--- C++ ---
class Solution {
public:
int minDistance(string word1, string word2) {
if (word1.size()==0) return word2.size();
if (word2.size()==0) return word1.size();
vector<vector<int>> E (word2.size()+1, vector<int>(word1.size()+1, 0));
for (int i=0; i<word1.size()+1; i++)
E[0][i] = i;
for (int j=0; j<word2.size()+1; j++)
E[j][0] = j;
for (int i=1; i<word2.size()+1; i++) {
for (int j=1; j<word1.size()+1; j++) { //note: j needs to start from index 1.
int tmp = min (E[i-1][j]+1, E[i][j-1]+1);
mtx[i][j] = min( tmp, (word2[i-1]==word1[j-1])?E[i-1][j-1] : E[i-1][j-1]+1 );
}
}
return E.back().back();
}
};
//--- Java ---
public class Solution {
public int minDistance(String word1, String word2) {
if (word1.length()==0) return word2.length();
if (word2.length()==0) return word1.length();
int [] dist = new int[word1.length()+1];
for (int i=0; i<dist.length; i++)
dist[i] = i;
for (int j=0; j<word2.length(); j++) {
int d0= dist[0];
int d1= 0;
dist[0] = j+1;
for (int i=1; i<dist.length; i++) {
d1 = dist[i];
if (word2.charAt(j) == word1.charAt(i-1)) {
dist[i] = d0;
} else {
dist[i] = Math.min(Math.min(d0+1, d1+1), dist[i-1]+1);
}
d0=d1;
}
}
return dist[dist.length-1];
}
}
Find K-th Element in a Sorted 2-Dimensional Array
[Question]
Suppose there is a 2 dimensional array MxN, data in each column and row is in ascending order. Find k-th smallest element in this array.
[Analysis]
Merge sort can resolve this problem. but it may not make sense to build a min-heap of size M, when M>>K.
The first three elements in left-top corner of the array (A(0,0), A(0,1), A(1,0) ) make a natural heap. So first, we build a size 3 min heap, using A[0,0], A[0,1], A[1,0]; then
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
pick up [i+1,j] and [i,j+1]).
3)Loop through 1),2) K-1 times; We got K-th elements at the root of the heap.
The time complexity is O ( K Log K ). For each loop, heap size increase at most one, so the heap size is at last K. And the code needs to run K loops.
Further analysis: the algorithm above works well when K<<M and K<<N. When K is close to M or N, or K> M or N, the heap's maximum size in algorithm is M+N. So the time complexity will become O ( K Log (M+N) ). The good solution for this problem is to select the heap first: use either columns (N), rows(M) or diagonals (K). Selection depends the minimum of three sizes. The complexity will be: O( K Log Min(M, N, K) ).
[Similar Questions]
(1) This looks similar but is actually different, to find a value in a sorted 2-Dimensional Array. That can be resolved in time O(N).
(2) Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Consider the following matrix:
// Binary search can apply on this question.
[Solution]
package com.mysrc.algortest;
import java.util.*;
public class MatrixSort implements TestCaseRunner {
class MatrixNode implements Comparable{
int x;
int y;
int value;
MatrixNode( int x, int y, int val) {
this.x = x;
this.y = y;
value = val;
}
public int compareTo(Object other) {
if (!(other instanceof MatrixNode)) {
throw new ClassCastException("Invalid object");
}
MatrixNode a = (MatrixNode) other;
if (this.value < a.value) return -1;
if (this.value > a.value) return 1;
return 0;
}
}
public int findKthElementInSortedMatrix(int[][] m, int k) {
PriorityQueue<MatrixNode> heap = new PriorityQueue<MatrixNode>();
heap.add(new MatrixNode(0,0, m[0][0]));
heap.add(new MatrixNode(0,1, m[0][1]));
heap.add(new MatrixNode(1,0, m[1][0]));
m[0][0] = -1;
m[0][1] = -1;
m[1][0] = -1;
MatrixNode head = null;
while (k-->0) {
head = heap.remove();
System.out.println("X,Y, V == " + head.x + "," + head.y + "," + head.value);
if (head.x < m.length-1 && m[head.x+1][head.y] != -1) {
heap.add(new MatrixNode(head.x+1, head.y, m[head.x+1][head.y]));
m[head.x+1][head.y] = -1;
}
if (head.y < m[0].length-1 && m[head.x][head.y+1] != -1) {
heap.add(new MatrixNode(head.x, head.y+1, m[head.x][head.y+1]));
m[head.x][head.y+1] = -1;
}
}
return head.value;
}
public boolean runTestCases() {
MatrixSort msort = new MatrixSort();
int[][] arr = {
{1, 3, 5, 7, 9, 11, 13, 15, 17},
{2, 6, 8, 12, 13, 14, 15, 16, 17},
{8, 10, 12, 14, 16, 18, 18, 18, 18},
{9, 10, 13, 15, 17, 19, 21, 23, 25},
{11, 12, 13, 19, 20, 21, 24, 28, 30},
{15, 16, 17, 19, 20, 22, 29, 30, 31},
{18, 19, 20, 21, 22, 23, 30, 31, 33}
};
msort.findKthElementInSortedMatrix(arr, 13);
return true;
}
}
Suppose there is a 2 dimensional array MxN, data in each column and row is in ascending order. Find k-th smallest element in this array.
[Analysis]
Merge sort can resolve this problem. but it may not make sense to build a min-heap of size M, when M>>K.
The first three elements in left-top corner of the array (A(0,0), A(0,1), A(1,0) ) make a natural heap. So first, we build a size 3 min heap, using A[0,0], A[0,1], A[1,0]; then
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
pick up [i+1,j] and [i,j+1]).
3)Loop through 1),2) K-1 times; We got K-th elements at the root of the heap.
The time complexity is O ( K Log K ). For each loop, heap size increase at most one, so the heap size is at last K. And the code needs to run K loops.
Further analysis: the algorithm above works well when K<<M and K<<N. When K is close to M or N, or K> M or N, the heap's maximum size in algorithm is M+N. So the time complexity will become O ( K Log (M+N) ). The good solution for this problem is to select the heap first: use either columns (N), rows(M) or diagonals (K). Selection depends the minimum of three sizes. The complexity will be: O( K Log Min(M, N, K) ).
[Similar Questions]
(1) This looks similar but is actually different, to find a value in a sorted 2-Dimensional Array. That can be resolved in time O(N).
(2) Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]Given target =
3, return true. // Binary search can apply on this question.
[Solution]
package com.mysrc.algortest;
import java.util.*;
public class MatrixSort implements TestCaseRunner {
class MatrixNode implements Comparable{
int x;
int y;
int value;
MatrixNode( int x, int y, int val) {
this.x = x;
this.y = y;
value = val;
}
public int compareTo(Object other) {
if (!(other instanceof MatrixNode)) {
throw new ClassCastException("Invalid object");
}
MatrixNode a = (MatrixNode) other;
if (this.value < a.value) return -1;
if (this.value > a.value) return 1;
return 0;
}
}
public int findKthElementInSortedMatrix(int[][] m, int k) {
PriorityQueue<MatrixNode> heap = new PriorityQueue<MatrixNode>();
heap.add(new MatrixNode(0,0, m[0][0]));
heap.add(new MatrixNode(0,1, m[0][1]));
heap.add(new MatrixNode(1,0, m[1][0]));
m[0][0] = -1;
m[0][1] = -1;
m[1][0] = -1;
MatrixNode head = null;
while (k-->0) {
head = heap.remove();
System.out.println("X,Y, V == " + head.x + "," + head.y + "," + head.value);
if (head.x < m.length-1 && m[head.x+1][head.y] != -1) {
heap.add(new MatrixNode(head.x+1, head.y, m[head.x+1][head.y]));
m[head.x+1][head.y] = -1;
}
if (head.y < m[0].length-1 && m[head.x][head.y+1] != -1) {
heap.add(new MatrixNode(head.x, head.y+1, m[head.x][head.y+1]));
m[head.x][head.y+1] = -1;
}
}
return head.value;
}
public boolean runTestCases() {
MatrixSort msort = new MatrixSort();
int[][] arr = {
{1, 3, 5, 7, 9, 11, 13, 15, 17},
{2, 6, 8, 12, 13, 14, 15, 16, 17},
{8, 10, 12, 14, 16, 18, 18, 18, 18},
{9, 10, 13, 15, 17, 19, 21, 23, 25},
{11, 12, 13, 19, 20, 21, 24, 28, 30},
{15, 16, 17, 19, 20, 22, 29, 30, 31},
{18, 19, 20, 21, 22, 23, 30, 31, 33}
};
msort.findKthElementInSortedMatrix(arr, 13);
return true;
}
}
Thursday, April 19, 2012
Anagram Strings
[Question]:
Given a dictionary of words, find groups of anagram words.
[Analysis]:
Anagram words are words that share the same group of letters. Hash on the group of (sorted) letters to find anagram words in a dictionary.
[Solution]:
public static List<List<String>> getAnagrams(String[] dict)
{
Map<String, List<String>> hash = new HashMap();
for (String s: dict)
{
ArrayList<String> arrlist = new ArrayList<String>();
char[] chars = s.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
if (!hash.containsKey(sorted)) {
hash.put(sorted, new ArrayList<String>());
}
hash.get(sorted).add(s);
}
List<List<String>> ret = new ArrayList<List<String>>();
for(List<String> list: hash.values()) {
if (list.size()>1) ret.add(list);
}
return ret;
}
Given a dictionary of words, find groups of anagram words.
[Analysis]:
Anagram words are words that share the same group of letters. Hash on the group of (sorted) letters to find anagram words in a dictionary.
[Solution]:
public static List<List<String>> getAnagrams(String[] dict)
{
Map<String, List<String>> hash = new HashMap();
for (String s: dict)
{
ArrayList<String> arrlist = new ArrayList<String>();
char[] chars = s.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
if (!hash.containsKey(sorted)) {
hash.put(sorted, new ArrayList<String>());
}
hash.get(sorted).add(s);
}
List<List<String>> ret = new ArrayList<List<String>>();
for(List<String> list: hash.values()) {
if (list.size()>1) ret.add(list);
}
return ret;
}
//--- A C++ code, which is shorter. ---
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
unordered_map<string, vector<string>> map;
for (auto s: strs) {
string sorted = s;
sort(sorted.begin(), sorted.end());
map[sorted].push_back(s);
}
vector<string> rslt;
for (auto pair: map){
if (pair.second.size()>1)
rslt.insert(rslt.end(), pair.second.begin(), pair.second.end());
}
return rslt;
}
};
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
unordered_map<string, vector<string>> map;
for (auto s: strs) {
string sorted = s;
sort(sorted.begin(), sorted.end());
map[sorted].push_back(s);
}
vector<string> rslt;
for (auto pair: map){
if (pair.second.size()>1)
rslt.insert(rslt.end(), pair.second.begin(), pair.second.end());
}
return rslt;
}
};
Wednesday, April 18, 2012
Find K-th element in two sorted arrays
[Question]:
Find the k-th element in two sorted arrays.
[Analysis]:
The k-th element exists in A[0, ... , k-1] and B[0, ..., k-1]. Suppose m of the k elements are in A, then A[m]> B[k-m-1], B[k-m]>A[m-1]. The k-th element is MAX (A[m-1], B[k-m-1]). Use binary search to find such m. Time complexity is O(log k).
[Alternative Question]:
Find the median of two sorted arrays. In this case, k = (M+N)/2, M, N are lengths of A and B.
[Solution]:
//
//Find the k-th element.
//
public static int findKthElementOfArrays(int[] a, int[] b, int k) {
assert k>0;
assert a.length + b.length >= k;
int low = Math.max(0, k-b.length);
int high= Math.min(k, a.length);
int m = 0;
while (low < high) {
m = low + (high-low)/2;
if (k-m-1>=0 && a[m]<b[k-m-1]) {
low = m+1;
}
else if (m>0 && k-m <b.length && b[k-m]<a[m-1]) {
high = m;
}
else {
low = m;
break;
}
}
if (low == 0) return b[k-1];
if (low == k) return a[k-1];
return Math.max(a[low-1], b[k-low-1]);
}
//
// Find the median.
//
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> &a=nums1.size()<nums2.size()?nums1:nums2,
&b = a==nums1?nums2:nums1;
auto median=[](vector<int>& x) {
int i = x.size()/2;
return x.size()%2?(double)x[i]: (x[i-1]+x[i])/2.0;
};
if (a.empty()) return median(b);
if (b.empty()) return median(a);
int m=a.size(), n=b.size(), k=(m+n)>>1;
int lo=max(0,k-n), hi=min(m, k);
while (lo<hi) {
int mid = (lo+hi)>>1;
if (k-mid-1>=0 && b[k-mid-1]>a[mid])
lo = mid+1;
else if (mid-1>=0 && b[k-mid]<a[mid-1])
hi = mid;
else {
lo = mid;
break;
}
}
int upper = (lo==m)?b[k-lo]:(k-lo)==n?a[lo]:min(a[lo],b[k-lo]);
int lower = (lo==0)?b[k-1]:(lo==k)?a[k-1]:max(a[lo-1],b[k-lo-1]);
return (m+n)&0x01? upper: (upper+lower)/2.0;
}
};
Find the k-th element in two sorted arrays.
[Analysis]:
The k-th element exists in A[0, ... , k-1] and B[0, ..., k-1]. Suppose m of the k elements are in A, then A[m]> B[k-m-1], B[k-m]>A[m-1]. The k-th element is MAX (A[m-1], B[k-m-1]). Use binary search to find such m. Time complexity is O(log k).
[Alternative Question]:
Find the median of two sorted arrays. In this case, k = (M+N)/2, M, N are lengths of A and B.
[Solution]:
//
//Find the k-th element.
//
public static int findKthElementOfArrays(int[] a, int[] b, int k) {
assert k>0;
assert a.length + b.length >= k;
int low = Math.max(0, k-b.length);
int high= Math.min(k, a.length);
int m = 0;
while (low < high) {
m = low + (high-low)/2;
if (k-m-1>=0 && a[m]<b[k-m-1]) {
low = m+1;
}
else if (m>0 && k-m <b.length && b[k-m]<a[m-1]) {
high = m;
}
else {
low = m;
break;
}
}
if (low == 0) return b[k-1];
if (low == k) return a[k-1];
return Math.max(a[low-1], b[k-low-1]);
}
//
// Find the median.
//
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> &a=nums1.size()<nums2.size()?nums1:nums2,
&b = a==nums1?nums2:nums1;
auto median=[](vector<int>& x) {
int i = x.size()/2;
return x.size()%2?(double)x[i]: (x[i-1]+x[i])/2.0;
};
if (a.empty()) return median(b);
if (b.empty()) return median(a);
int m=a.size(), n=b.size(), k=(m+n)>>1;
int lo=max(0,k-n), hi=min(m, k);
while (lo<hi) {
int mid = (lo+hi)>>1;
if (k-mid-1>=0 && b[k-mid-1]>a[mid])
lo = mid+1;
else if (mid-1>=0 && b[k-mid]<a[mid-1])
hi = mid;
else {
lo = mid;
break;
}
}
int upper = (lo==m)?b[k-lo]:(k-lo)==n?a[lo]:min(a[lo],b[k-lo]);
int lower = (lo==0)?b[k-1]:(lo==k)?a[k-1]:max(a[lo-1],b[k-lo-1]);
return (m+n)&0x01? upper: (upper+lower)/2.0;
}
};
Subscribe to:
Posts (Atom)