Java O(N) solution


  • 0
    R

    From the question description of "1 ≤ a[i] ≤ n (n = size of array)", we can get a sense of this question can be solved with traverse the array using the element value as index.
    But the "-" part is a little bit tricky to think of.

    public class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> ans=new ArrayList<Integer>();
            for(int i=0;i<nums.length;i++){
                if(nums[Math.abs(nums[i])-1]<0) ans.add(Math.abs(nums[i]));
                else nums[Math.abs(nums[i])-1]=-nums[Math.abs(nums[i])-1];
            }
            return ans;
        }
    }
    

Log in to reply
 

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