Explain to me why this C# O(N^2) solution is faster than editorial O(N) solution


  • 0
    D
    public class Solution {
        public void MoveZeroes(int[] nums) {
    	int start = 0;
    	while(start < nums.Length)
    	{
    		int zero = GetFirstZeroIndex(nums, start);
    		if (zero == -1) break;
    		int other = GetFirstNonZeroIndex(nums, zero + 1);
    		if (other == -1) break;
    
    		Swap(nums, zero, other);		
    		start = zero + 1;
    	}        
        }
    
    	static int GetFirstZeroIndex(int[] nums, int start)
    	{
    		for(int i = start; i < nums.Length; i++)
    		{
    			if(nums[i] == 0) return i;
    		}
    		return -1;
    	}
    
    	static int GetFirstNonZeroIndex(int[] nums, int start)
    	{
    		for(int i = start; i < nums.Length; i++)
    		{
    			if(nums[i] != 0) return i;
    		}
    		return -1;
    	}
    
    	static void Swap<T>(T[] nums, int a, int b)
    	{
    		//TODO: Assert a and b are valid within range
    		T temp = nums[b];
    		nums[b] = nums[a];
    		nums[a] = temp;
    	}
    }
    

  • 0
    A

    The time complexity is not directly impacting every single runtime speed. It is highly up to the each specific test case. If you take a look at those sorting algorithm wiki, you will see their efficiencies are floating based on worst case or best case.


Log in to reply
 

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