C# O(n) and O(1) space keep swap number with is not in right position, then scan to find disappears


  • 0
    Y
    public class Solution {
        public IList<int> FindDisappearedNumbers(int[] nums) {
            //O(n) and O(1) space
            int i=0;
            List<int> res=new List<int>();
            while(i<nums.Length)
            {
                if(nums[nums[i]-1]==nums[i])
                    i++;
                else
                    swap(nums,i,nums[i]-1);
            }
            for(int j=0;j<nums.Length;j++)
            {
                if(nums[j]!=j+1)
                    res.Add(j+1);
            }
            return res;
        }
        private void swap(int[] nums,int i, int j)
        {
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
    }

Log in to reply
 

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