5-line Java Easy-understanding


  • 41
    H
    public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> res = new ArrayList<>();
            int n = nums.length;
            for (int i = 0; i < nums.length; i ++) nums[(nums[i]-1) % n] += n;
            for (int i = 0; i < nums.length; i ++) if (nums[i] <= n) res.add(i+1);
            return res;
        }
    

  • 1
    C

    just mark the positions without changing values! great!


  • 5
    Y

    @hu19 You may want to consider the overflow case.


  • 1
    H

    @yuhaowang001 Yes, correct. With the range of number increasing, I would like to use Long or BigInteger to avoid overflow. Thanks for pointing this!


  • 0
    H

    perfect, you can change back the value after find out result;


  • 0
    H

    @huheng Yes, we can simply traverse array again and for each element, call nums[i] = nums[i] % n; to restore. Thanks for pointing out!


  • 0
    D

    Nice solution.


  • 1
    X

    @hu19 Nice solution! For it is not 0 based array, the step nums[i] = nums[i] % n makes error when the original value nums[i] == n. nums[(nums[i]-1) % (n+1)] += n+1 and call nums[i] = nums[i] % (n+1) will work.


  • 0

    @xixin Sharp!


  • 0

    @hu19 interesting approach, a little trickier than the standard which marks found number by negating their corresponding index.

    I suppose you could handle your overflow case with this change in your second loop as the overflow for int will wrap to a negative number.

    if (nums[i] > 0 && nums[i] <= n) res.add(i+1);
    

    Here's the negate approach

        public IList<int> FindDisappearedNumbers(int[] nums) 
        {
            // set index to negative for each number
            for (int i = 0; i < nums.Length; i++)
            {
                int x = Math.Abs(nums[i]);
                nums[x-1] = -Math.Abs(nums[x-1]);
            }
            
            // any index with positive number is missing
            IList<int> missing = new List<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] > 0)
                {
                    missing.Add(i + 1);
                }
            }
            
            return missing;
        }
    

  • 0
    T

    perfect, but why @hu19


  • 0
    G

    @hu19 good idea,I enjoy it,and thisis my code:

    public class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            Set<Integer> st=new HashSet<Integer>();
            List<Integer> rt=new ArrayList<Integer>();
            for(int ci:nums){
                st.add(ci);
            }
            for(int i=1;i<=nums.length;i++){
                if(!st.contains(i)){
                  rt.add(i);
                }}
            return rt;
        }}
    

  • 0
    S

    @Gene20 The question mentions without using an extra memory space. Is Set allowed in that? because initially even I thought of using a HashMap


  • 0

    what does "nums[(nums[i]-1) % n] += n" means?


  • 0
    P

    By (nums[i]-1) % n, we can calculate the original number in the array.
    For example, [4, 3, 2, 7, 8, 2, 3, 1]
    if i == 1, nums[i] = 3, nums[i]-1 = 2, we will visit the first 2,
    after visit this 2 will become 10, since n is 8
    if i == 2, nums[i] = 10, nums[i]-1 = 9, which is wrong
    Thus we need 10 % 8 = 2 to calculate the original number to get the index.
    if i ==2, (nums[i]-1) % n = 1, we can visit correctly


  • 0
    C
    This post is deleted!

  • 0
    A

    @hu19 amazing....


  • 0
    B

    I just wonder that how could you come up with this solution???


Log in to reply
 

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