Swift solution using modified quick-select with explanation, 18ms


  • 0
    S
    class Solution {
        
        func hIndex(_ citations: [Int]) -> Int {
            
            if citations.isEmpty {
                return 0
            }
            
            var citations = citations
            
            var from = 0
            var to = citations.count - 1
            var lo = 0
            var pi = 0
            var hi = 0
            var pivot = 0
            
            while true {
                lo = from
                pi = from
                hi = to
                pivot = citations[(from + to) / 2]
                
                // quick select to find xth highest citation count
                while pi <= hi {
                    if citations[pi] < pivot {
                        if pi != hi { swap(&citations[pi], &citations[hi]) }
                        hi -= 1
                    } else if citations[pi] > pivot {
                        if pi != lo { swap(&citations[pi], &citations[lo]) }
                        lo += 1
                        pi += 1
                    } else {
                        pi += 1
                    }
                }
                
                // if x-th biggest citation count is >= it's index (indexed from 1)
                if citations[lo] >= lo + 1 {
                    // process the right part if there are still some elements
                    if lo == to {
                        return lo + 1
                    }
                    from = lo + 1
                } else {
                    // otherwise x-th highest citation is not enough
                    // process the left part if there are still some elements
                    if lo == from {
                        return lo
                    }
                    to = lo - 1
                }
            }
        }
    }
    

Log in to reply
 

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