sort binary array with minimum time complexity

Question

Anónimo · Accepted Answer

Maintain two counters, one for 0 and another for 1. Start from array[0] and go on till end and increment counts if zero or one whichever you encounter. Overwrite the array with number of zeros and then number of ones. "counting sort". O(n)

hivehome · Answer

int[] sortBinary(int[] nums) {
        if(nums == null || nums.length ==0)
            return nums;
        int left = 0, right = nums.length -1;
        while(left < right) {
            if(nums[left] == 0)
                left++;
            if(nums[right] == 1)
                right--;
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }

Anónimo · Answer

traverse array in one for loop with one index from start and one from end.
move all 0's on one end and 1's on other end using these indexed.
The minimum time complexity is O(n/2)

Anónimo · Answer

void
sort(char A[], int len)
{
   int ones = len - 1;
   int zeroes = 0;

   while (zeros < ones) {
      while (A[zeroes] == 0)
         zeroes++;
      while (A[ones] == 1)
         ones--;
      swap(A+zeroes, A+ones);
      zeroes++;
      ones--;
   }
}

Apple

Pregunta de entrevista de Apple

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo