Java O(n) time and O(1) space solution.


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

Log in to reply
 

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