Swift Solution by randomized selection


  • 0
    J

    import Foundation

    class Solution {
    func thirdMax(_ nums: [Int]) -> Int {
    let unique = Array(Set(nums))

        if unique.count <= 2 {
            return unique.max()!
        }
    
        if unique.count == 3 {
            return unique.min()!
        }
        
        return self.rSelect(items: unique, at: UInt(unique.count - 3))
    }
    
    private func rSelect<T: Comparable>(items: [T], at pos: UInt) -> T {
        assert(!items.isEmpty)
    
        if items.count == 1 {
            return items[0]
        }
    
        let partitionRet = self.partition(items)
        let pivotElePos = UInt(partitionRet.1.count)
        if pivotElePos == pos {
            return partitionRet.0
        }
    
        if pivotElePos > pos {
            return self.rSelect(items: partitionRet.1, at: pos)
        } else {
            return self.rSelect(items: partitionRet.2, at: pos - pivotElePos - 1)
        }
    }
    
    private func partition<T: Comparable>(_ items: [T]) -> (T, [T], [T]) {
        var partitionItems = items
        
        let pivotIndex = Int(random() % items.count)
        //let pivotIndex = Int(arc4random() % UInt32((items.count)))
        if pivotIndex != 0 {
            swap(&(partitionItems[partitionItems.startIndex]), &(partitionItems[pivotIndex]))
        }
        
        let pivotEle = partitionItems[partitionItems.startIndex]
        var i = partitionItems.startIndex + 1
        for j in (partitionItems.startIndex + 1)..<partitionItems.endIndex {
            if partitionItems[j] < pivotEle {
                if j != i {
                    swap(&(partitionItems[i]), &(partitionItems[j]))
                }
                
                i += 1
            }
        }
        
        let pivotEleIndex = i - 1
        
        if pivotEleIndex != partitionItems.startIndex {
            swap(&(partitionItems[partitionItems.startIndex]), &(partitionItems[pivotEleIndex]))
        }
        
        let leftItems = partitionItems[partitionItems.startIndex..<pivotEleIndex]
        let rightItems = partitionItems[(pivotEleIndex+1)..<partitionItems.endIndex]
        
        return (partitionItems[pivotEleIndex], [T](leftItems), [T](rightItems))
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.