In theLeetCode [Problem #4](leetcode.com/problems/median-of-two-sorted-.. the inputs are two arrays sorted in an ascending order. The constraints in the problems are.
- Each of the arrays may have 0 to 1000 elements.
- Each elements can have value ranging from -106 to 106.
- And finally, the algorithm should find the median in
O(log(m+n))
time, wherem
andn
are lengths of the input arrays.
Median
In statistics, the median is the middle number in the set of sorted numbers. For example, in the set of numbers [1,2,3,4,5]
, 3 is the median. But if there are even numbers in the set, then we find the average of the middle number and the next number. For example, in the set of numbers [1,2,3,4,5,6]
, the median is (3+4)/2
i.e., 3.5.
Solution
One of the solutions for this problem is we create a new array with a length equal to the sum of the lengths of two input arrays. Copy both arrays into the new array and then sort it to find the median. In this solution copying each array into the new array would take O(m+n)
and sorting the new array would take O(log(m+n))
. This could be an acceptable solution.
However, we can do better with a double-linked list. In this list, we insert elements such that smaller numbers are always pushed to the left side of the node and larger elements are always inserted to the right. But we would always return the mid-value node. The implementation is given below.
type Node struct {
Value int
next *Node
prev *Node
}
func (node *Node) LastNode() *Node {
if node.next == nil {
return node
}
return node.next.LastNode()
}
func (node *Node) FirstNode() *Node {
if node.prev == nil {
return node
}
return node.prev.FirstNode()
}
func (node *Node) Next(value int) *Node {
if value < node.Value {
newNode := &Node{Value: value, next: node, prev: node.prev}
node.prev.next = newNode
node.prev = newNode
return node.LastNode()
}
if node.next == nil {
node.next = &Node{Value: value, next: nil, prev: node}
return node.next
}
return node.next.Next(value)
}
func (node *Node) Prev(value int) *Node {
if value > node.Value {
newNode := &Node{Value: value, next: node.next, prev: node}
node.next.prev = newNode
node.next = newNode
return node.FirstNode()
}
if node.prev == nil {
node.prev = &Node{Value: value, next: node, prev: nil}
return node.prev
}
return node.prev.Prev(value)
}
func Push(node *Node, value int) *Node {
if node == nil {
return &Node{Value: value}
}
if value >= node.Value {
return node.Next(value)
}
node.Prev(value)
return node
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
var endNode *Node
maxLen := len(nums1)
if maxLen < len(nums2) {
maxLen = len(nums2)
}
for i := 0; i < maxLen; i++ {
if i < len(nums1) {
endNode = Push(endNode, nums1[i])
}
if i < len(nums2) {
endNode = Push(endNode, nums2[i])
}
}
lenOfArrs := len(nums1) + len(nums2)
median := int((lenOfArrs-lenOfArrs%2)/2) + 1
for i := lenOfArrs; i > median && endNode.prev != nil; i-- {
endNode = endNode.prev
}
if lenOfArrs%2 == 0 {
return (float64(endNode.Value+endNode.prev.Value) / 2.0)
}
return float64(endNode.Value)
}