Swift中的O（log n）時間中的中間數

Question

我有一個算法找到O(log n)中兩個大的排序數組的中值，但是如何在相同的時間複雜度下返回給出中位數的中間兩個數？例如：給定array1 = [1, 2, 3, 4, 50, 62, 77]和array2 = [ 17, 27, 33, 89, 600, 700, 900]，應返回33,50。

我的代碼找到中位數：我無法修改它只返回中位數。

class FindMedianSortedArrays { 

    func findMedian(input: [Int], startIndex: Int, endINdex: Int) -> Double { 

     let indexDifference = (endINdex - startIndex) 
     if indexDifference % 2 == 0 { 
      return Double(input[startIndex + (indexDifference/2)]) 
     } else { 
      return Double(input[startIndex + (indexDifference/2)] + input[startIndex + (indexDifference/2) + 1])/2.0 
     } 
    } 



    func findMedianInSortedArray(inputA: [Int], inputB: [Int], startIndexA: Int, endIndexA: Int, startIndexB: Int, endIndexB: Int) -> Double { 
     var startIndexA = startIndexA 
     var endIndexA = endIndexA 
     var startIndexB = startIndexB 
     var endIndexB = endIndexB 

     if ((endIndexA - startIndexA) < 0) || ((endIndexB - startIndexB) < 0) { 
      print("Invalid Input") 
     } 

     if (endIndexA - startIndexA == 0) && (endIndexB - startIndexB == 0) { 
      return Double(inputA[0] + inputB[0])/2.0 
     } 

     if endIndexA - startIndexA == 1 && endIndexB - startIndexB == 1 { 
      return Double(max(inputA[startIndexA], inputB[startIndexB]) + min(inputA[endIndexA], inputB[endIndexB]))/2.0 
     } 

     let medianA: Double = findMedian(input: inputA, startIndex: startIndexA, endINdex: endIndexA) 
     let medianB: Double = findMedian(input: inputB, startIndex: startIndexB, endINdex: endIndexB) 

     //our second base case 
     if medianB == medianA { 
      return medianB //return either medianA or medianB 
     } 

     //since medianA <= median <= medianB, 
     //eliminate elements less than medianA and greater than medB 
     if medianA < medianB { 
      if((endIndexA - startIndexA) % 2 == 0) { 
      startIndexA = startIndexA + (endIndexA - startIndexA)/2 
      endIndexB = startIndexB + (endIndexB - startIndexB)/2 
      } else { 
       startIndexA = startIndexA + (endIndexA - startIndexA)/2 
       endIndexB = startIndexB + (endIndexB - startIndexB)/2 + 1 
      } 
     } 

     //since medianB <= median <= medianA, eliminate elements less 
     //than medianB and greater than medianA to narrow down the search. 

     else { 
      if ((endIndexB - startIndexB) % 2 == 0) { 
       startIndexB = startIndexB + (endIndexB - startIndexB)/2 
       endIndexA = startIndexA + (endIndexA - startIndexA)/2 + 1 
      } 
     } 
     return findMedianInSortedArray(inputA:inputA,  inputB: inputB, startIndexA: startIndexA, endIndexA:endIndexA, startIndexB: startIndexB, endIndexB: endIndexB) 
    } 
} 

Answer 1

//: Playground - noun: a place where people can play 

import Foundation 

class FindMiddleNumbersInSortedArray { 

    func findMedianInSortedArray(inputA: [Int], inputB: [Int], startIndexA: Int, endIndexA: Int, startIndexB: Int, endIndexB: Int) -> [Int] { 

     var medianNumbers:[Int] = [] 
     //make sure arrays have the same size 
     guard inputA.count == inputB.count else { return medianNumbers } 

     var startIndexA = startIndexA 
     var endIndexA = endIndexA 
     var startIndexB = startIndexB 
     var endIndexB = endIndexB 
     //make sure the user provides right indexes: start and end 
     if ((endIndexA - startIndexA) < 0) || ((endIndexB - startIndexB) < 0) { 
      fatalError("Invalid Input indexes") 
     } 
     //if medianA == medianB, we are done, we can append either one twice or both 
     if (endIndexA - startIndexA == 0) && (endIndexB - startIndexB == 0) { 
      medianNumbers.append(inputA[0]) 
      medianNumbers.append(inputB[0]) 
      return medianNumbers  } 
     /*if the size == 1, then median = max(ar1[0], ar2[0]) + min(ar1[1], 
     ar2[1]))/2.0 */ 
     if endIndexA - startIndexA == 1 && endIndexB - startIndexB == 1 { 
      medianNumbers.append(max(inputA[startIndexA], inputB[startIndexB])) 
      medianNumbers.append(min(inputA[endIndexA], inputB[endIndexB])) 
      return medianNumbers 
     } 

     let medianA = findMedian(input: inputA, startIndex: startIndexA, endIndex: endIndexA) 
     let medianB = findMedian(input: inputB, startIndex: startIndexB, endIndex: endIndexB) 

     if medianB == medianA { 

      medianNumbers.append(Int(medianA)) 
      medianNumbers.append(Int(medianB)) 
      return medianNumbers  } 

     let medianAIndex = (startIndexA + endIndexA)/2 
     let medianBIndex = (startIndexB + endIndexB)/2 
     //if medianB>medianA, median is in inputA[n/2...n-1] & inputB[0...n/2] 
     if medianB > medianA { 
      if((endIndexA - startIndexA) % 2 == 0) { 
       startIndexA = medianAIndex 
       endIndexB = medianBIndex 
      } else { 
       startIndexA = medianAIndex 
       endIndexB = medianBIndex + 1 
      } 

      //else median is in inputA[0...n/2] and inputB[n/2...n-1] subarrays 
     } else { 
      if((endIndexA - startIndexA) % 2 == 0) { 
       endIndexA = medianAIndex 
       startIndexB = medianBIndex 
      } else { 
       endIndexA = medianAIndex + 1 
       startIndexB = medianBIndex 
      } 
     } 

     return findMedianInSortedArray(inputA: inputA, inputB: inputB, startIndexA: startIndexA, endIndexA: endIndexA, startIndexB: startIndexB, endIndexB: endIndexB) 
    } 

    func findMedian(input: [Int], startIndex: Int, endIndex: Int) -> Double { 
     let indexMid = (startIndex + endIndex)/2 
     let indexDifference = (endIndex - startIndex) 
     if indexDifference % 2 == 1 { 
      return Double(input[indexMid+1]+input[indexMid])/2.0 
     } else { 
      return Double(input[indexMid]) 
     } 
    } 


    //test the code 
    func testWithExample(inputA: [Int], inputB: [Int]) { 
     print("=====Example=====") 
     print("InputA: \(inputA)") 
     print("InputB: \(inputB)") 
     print("Median numbers: ", findMedianInSortedArray(inputA: inputA, inputB: inputB, startIndexA: 0, endIndexA: inputA.count - 1, startIndexB: 0, endIndexB: inputA.count - 1)) 
    } 

} 

//test the program 
let medianNumbers = FindMiddleNumbersInSortedArray() 
let input1 = [ 10, 20, 30, 40, 51, 61, 71] 
let input2 = [ 15, 25, 31, 86, 600, 700, 900] 
medianNumbers.testWithExample(inputA: input1, inputB: input2) 

Answer 2

查找兩個排序數組的中間數是O(n)。僞代碼示例：

index1 = 0 
index2 = 0 

for count = 0 to (array1.count + array2.count)/2 
    if array1[index1] < array2[index2] then 
     index1 = index1 + 1 
    else 
     index2 = index2 + 1 

median1 = array1[index1] 
median2 = array2[index2] 

以上樣本顯然是不完全正確的，不能處理的邊緣情況，但應該足以給你的總體思路。

Answer 3

更新的解決方案：

嘗試下面的代碼，我曾與下面的示例進行測試。

---

//tested examples 
example(inputA: [1, 2, 3, 4, 50, 62, 77], 
      inputB: [ 17, 27, 33, 89, 600, 700, 900]) 
// result: [33 50] 

example(inputA: [10, 11, 12, 13, 14, 20], 
      inputB: [10, 11, 12, 14, 20]) 
// result : [12, 13] 

example(inputA: [10, 11, 12, 13, 14, 800], 
      inputB: [10, 11, 12, 14, 20, 21, 900]) 
// result : [13, 14] 

example(inputA: [1, 2, 3, 4, 5], 
      inputB: [7, 8, 9, 10, 11]) 
// return [7, 5] 

func example(inputA: [Int], inputB: [Int]) { 
    print("---Example----") 
    print(inputA) 
    print(inputB) 
    print(findMedianInSortedArray(inputA: inputA, inputB: inputB, startIndexA: 0, endIndexA: inputA.count-1, startIndexB: 0, endIndexB: inputB.count-1)) 
} 

---

func findMedianInSortedArray(inputA: [Int], inputB: [Int], startIndexA: Int, endIndexA: Int, startIndexB: Int, endIndexB: Int) -> [Int] { 
    var findMedianNumArr:[Int] = [] 

    var startIndexA = startIndexA 
    var endIndexA = endIndexA 
    var startIndexB = startIndexB 
    var endIndexB = endIndexB 

    if ((endIndexA - startIndexA) < 0) || ((endIndexB - startIndexB) < 0) { 
     print("Invalid Input") 
    } 

    if (endIndexA - startIndexA == 0) && (endIndexB - startIndexB == 0) { 
     findMedianNumArr.append(inputA[0]) 
     findMedianNumArr.append(inputB[0]) 
     return findMedianNumArr 
    } 

    if endIndexA - startIndexA == 1 && endIndexB - startIndexB == 1 { 
     findMedianNumArr.append(max(inputA[startIndexA], inputB[startIndexB])) 
     findMedianNumArr.append(min(inputA[endIndexA], inputB[endIndexB])) 
     return findMedianNumArr 
    } 

    let medianA = findMedian(input: inputA, startIndex: startIndexA, endIndex: endIndexA) 
    let medianB = findMedian(input: inputB, startIndex: startIndexB, endIndex: endIndexB) 

    if medianB == medianA { 
     let medianArrA = findMedianArray(input: inputA, startIndex: startIndexA, endIndex: endIndexA) 
     let medianArrB = findMedianArray(input: inputB, startIndex: startIndexB, endIndex: endIndexB) 
     findMedianNumArr.append(contentsOf: medianArrA) 
     findMedianNumArr.append(contentsOf: medianArrB) 
     return findMedianNumArr 
    } 

    let medianAIndex = (startIndexA + endIndexA)/2 
    let medianBIndex = (startIndexB + endIndexB)/2 
    if medianB > medianA { 
     if((endIndexA - startIndexA) % 2 == 0) { 
      startIndexA = medianAIndex 
      endIndexB = medianBIndex 
     } else { 
      startIndexA = medianAIndex 
      endIndexB = medianBIndex + 1 
     } 
    } else { 
     if((endIndexA - startIndexA) % 2 == 0) { 
      endIndexA = medianAIndex 
      startIndexB = medianBIndex 
     } else { 
      endIndexA = medianAIndex + 1 
      startIndexB = medianBIndex 
     } 
    } 

    return findMedianInSortedArray(inputA: inputA, inputB: inputB, startIndexA: startIndexA, endIndexA: endIndexA, startIndexB: startIndexB, endIndexB: endIndexB) 
} 

func findMedian(input: [Int], startIndex: Int, endIndex: Int) -> Double { 
    let indexMid = (startIndex + endIndex)/2 
    let indexDifference = (endIndex - startIndex) 
    if indexDifference % 2 == 1 { 
     return Double(input[indexMid+1]+input[indexMid])/2.0 
    } else { 
     return Double(input[indexMid]) 
    } 
} 

func findMedianArray(input: [Int], startIndex: Int, endIndex: Int) -> [Int] { 
    var findMedianNumArr:[Int] = [] 

    let indexMid = (startIndex + endIndex)/2 
    let indexDifference = (endIndex - startIndex) 
    if indexDifference % 2 == 1 { 
     findMedianNumArr.append(input[indexMid+1]) 
    } 
    findMedianNumArr.append(input[indexMid]) 
    return findMedianNumArr 
}