There is char array of n length. Array can have elements only from of any order R, B, W.
You need to sort array so that order should R,B,W i.e. all R will come first followed by B and then W.
Constraints: Time complexity is O(n) and space complexity should be O(1) Assumption: You can assume one swap method is given with signature swap(int index1, int index2) that swaps number in unit time. method given to implement: public sort(char[]array);
Please leave your comments and suggestions that improves the logic above.
Constraints: Time complexity is O(n) and space complexity should be O(1) Assumption: You can assume one swap method is given with signature swap(int index1, int index2) that swaps number in unit time. method given to implement: public sort(char[]array);
public static void sort(char[] arr){ int rIndex = 0, wIndex = arr.length -1; for (int i = 0 ; i <= wIndex; ){ if ( arr[i] == 'R' ){ swap(arr, i , rIndex ++ ); i ++ ; } else if (arr[i] == 'W' ){ swap(arr, i , wIndex -- ); }else{ i ++; } } } //a dummy implementation just for testing sake private static void swap(char[] arr, int index1, int index2){ char temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; }
No comments:
Post a Comment