Bucket Sort - O(N). Generalize the question - if multiple number can be duplicate, find all duplicates


  • 0
    C

    The forum has two solutions1) Loop detection, 2) Binary Search. Throw in another idea, O(N), using bucket sort. Consider the number n belong to bucket num[n-1].

    When we put each number in their bucket. If duplicate exists, then we should find nums[nums[i]-1]==nums[i], otherwise, we should be able to traverse the array in O(N) time.

    public class Solution {
        public int findDuplicate(int[] nums) {
            for(int i=0;i<nums.length;i++){
                while(nums[i]!=i+1){
                    int j = nums[i]-1;
                    if(nums[i] == nums[j]) return nums[i];
                    else swap(nums, i, j);
                }
            }
            //not found
            return 0;
        }
        
        private void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

  • 2
    A
    1. You must not modify the array (assume the array is read only).

  • 0
    C

    this post is only for idea exploration, as the description mentioned. Not necessarily all discussions has to fit 100% of the proposed constrains.


Log in to reply
 

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