Swift solution - Binary Search, Two Pointers


  • 0
    class Solution {
        func findDuplicate_BinarySearch(_ nums: [Int]) -> Int {
            var left = 1
            var right = nums.count - 1
            var middle = 0
            var count = 0
            
            while left < right {
                middle = left + (right - left) / 2
                count = 0
                for num in nums {
                    if num <= middle {
                        count += 1
                    }
                }
                if count <= middle {
                    left = middle + 1
                } else {
                    right = middle
                }
            }
            
            return left
        }
        
        func findDuplicate_TwoPointers(_ nums: [Int]) -> Int {
            if nums.count < 2 {
                return -1
            }
            
            var slow = nums[0]
            var fast = nums[nums[0]]
            
            while slow != fast {
                slow = nums[slow]
                fast = nums[nums[fast]]
            }
            fast = 0
            while fast != slow {
                fast = nums[fast]
                slow = nums[slow]
            }
            
            return slow
        }
    }
    

Log in to reply
 

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