How To Find the Duplicate Number In Java

Question:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]

Output: 2

Example 2:

Input: nums = [3,1,3,4,2]

Output: 3

Approach 1:

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

Approach 2:

public static int findDuplicate_set(int[] nums) {
    Set <Integer> set = new HashSet<>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (!set.add(nums[i])) {
            return nums[i];
        }
    }
    return len;
}

 

Leave a Reply

Discover more from Start Programming | Step-by-Step Guide

Subscribe now to keep reading and get access to the full archive.

Continue reading