5-line Java Easy-understanding


  • 45
    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....


  • 1
    B
    This post is deleted!

Log in to reply
 

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