Reorder and count non-zero int in an array


  • 1
    X

    Giving an array of integers, such as [1, 0, 3, 4, 5, 0, ...],
    provide a piece of code that returns the non-zero elements in the array, and reorder
    the array with all these non-zero elements to the left, such as [1,3,4,5, X,X,X,X....]
    the order of non-zero elements does not matter and the elements on the right of the array do not matter.


  • 0
    S

    this code will move all zero to the right,

    public void MoveZeroes(int[] nums) {
          var stack = new Stack<int>();
            int zeros = 0;
    
            for (var i = 0; i < nums.Length; i++)
            {
                if (nums[i] == 0)
                {
                    zeros++;
                    continue;
                }
    
                stack.Push(nums[i]);
            }
    
            for (var i = nums.Length - 1; i > nums.Length - 1 - zeros; i--)
            {
                nums[i] = 0;
            }
    
            for (var i = nums.Length -1 - zeros; i >= 0; i--)
            {
                nums[i] = stack.Pop();
            }
    }

  • 0

    Actually, this is a duplicate of Move Zeros: https://leetcode.com/problems/move-zeroes/.


  • 0

    Too complex, we can do it in one pass :)


  • 0
    D
        int index = 0;
        for (int i = 0 ; i != nums.length; i++) {
            if (nums[i] == 0) {
                
            } else {
                nums[index] = nums[i];
                index++;
            }
        }
        
        for (int i = index ; i != nums.length; i++) {
            nums[i] = 0;
        }

  • 0

    this is similar to picking the pivot in quick sort, it's doable in one pass and O(1) space

    int[] order(int[] a) {
    		int i = 0;
    		int j = a.length - 1;
    
    		while (i <= j) {
    			while (j >= 0 && a[j] == 0)
    				j--;
    			while (i < a.length && a[i] != 0)
    				i++;
    			if(i <= j) {
    				a[i] = a[i] ^ a[j];
    				a[j] = a[i] ^ a[j];
    				a[i] = a[i] ^ a[j];
    			}
    		}
    
    		return Arrays.copyOfRange(a, 0, i);
    	}

Log in to reply
 

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