sort binary array with minimum time complexity

Question

Utilisateur anonyme · 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;
    }

Utilisateur anonyme · 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)

Utilisateur anonyme · 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

Question d’entretien chez Apple

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois