O(n) time & O(1) space easy to understand Java solution


  • 0
    R

    The main idea is comparing nums[0] with the element in its destination nums[nums[0]]. If the position is taken, then nums[0] is the duplicate element. Otherwise, swap it to the destination, and continue on the previous process. The duplicate element can be detected with at most m steps.

    class Solution {
        public int findDuplicate(int[] nums) {
            int m = nums.length;
            for(int i = 0; i < m; ++i) {
                int temp = nums[nums[0]];
                if(nums[0] == temp) {
                    return nums[0];
                } else {
                    nums[nums[0]] = nums[0];
                    nums[0] = temp;
                }
            }
            return -1;
        }
    }
    

    Binary Search Solution with the idea from https://discuss.leetcode.com/topic/27420/java-o-1-space-using-binary-search.

    class Solution {
        public int findDuplicate(int[] nums) {
            int start = 1, end = nums.length - 1;
            while(start < end) {
                int mid = start + ((end - start) >> 1);
                int count = 0;
                for(int n : nums) {
                    if(n <= mid) {
                        ++count;
                    }
                }
                if(count <= mid) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            return start;
        }
    }
    

Log in to reply
 

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