fueanta

LeetCode 283: Move Zeroes.

Mar 24th, 2020
167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Given an array nums, write a function to move all 0's to the end of it while maintaining
  3. the relative order of the non-zero elements.
  4.  
  5. Example:
  6. --------
  7. Input: [0,1,0,3,12]
  8. Output: [1,3,12,0,0]
  9.  
  10. Note:
  11. -----
  12. 1. You must do this in-place without making a copy of the array.
  13. 2. Minimize the total number of operations.
  14. */
  15.  
  16. namespace Problems.LeetCode.Array.MoveZeroes_283
  17. {
  18.     public class Solution
  19.     {
  20.         /// <summary>
  21.         ///     Moves all zeros to the end of an array.
  22.         ///     Moves non zeros to the left first then fills the rest with zeros.
  23.         ///     Time complexity : O(n)
  24.         ///     Space complexity : O(1)
  25.         /// </summary>
  26.         /// <param name="nums">An array of integers.</param>
  27.         public void MoveZeroes(int[] nums)
  28.         {
  29.             var insertAt = 0;
  30.  
  31.             for (var i = 0; i < nums.Length; i++)
  32.                 if (nums[i] != 0)
  33.                     nums[insertAt++] = nums[i];
  34.  
  35.             while (insertAt < nums.Length)
  36.                 nums[insertAt++] = 0;
  37.         }
  38.  
  39.         /// <summary>
  40.         ///     Moves all zeros to the end of an array.
  41.         ///     Uses two pointers and swapping.
  42.         ///     Time complexity : O(n)
  43.         ///     Space complexity : O(1)
  44.         /// </summary>
  45.         /// <param name="nums">An array of integers.</param>
  46.         public void MoveZeroes2(int[] nums)
  47.         {
  48.             var insertAt = 0;
  49.  
  50.             for (var i = 0; i < nums.Length; i++)
  51.             {
  52.                 if (nums[i] != 0)
  53.                 {
  54.                     var temp = nums[insertAt];
  55.                     nums[insertAt++] = nums[i];
  56.                     nums[i] = temp;
  57.                 }
  58.             }
  59.         }
  60.     }
  61. }
RAW Paste Data