satyen.shimpi
BAN USERfind the greatest element in array(index 0 to n) and move it to beginning of subarray (to index 1). Then in remaining subarray (index 1 to n) find the smallest element and move it to begining of subarray (to index 2).
recurse this solution to remaining subarray starting from index 2 to n.
public class SortIntegers{
public void sortAlternate(int[] nums, int startIndx, int endIndx){
if(startIndx >= endIndx) return;
greatestFirst(nums, startIndx, endIndx);
smallestFirst(nums, ++startIndx, endIndx);
sortAlternate(nums, ++startIndx, endIndx);
}
public void greatestFirst(int[] nums, int startIndx, int endIndx){
for(int i=startIndx; i< endIndx; i++){
if(nums[i] > nums[startIndx])
swap(nums, i, startIndx);
}
}
public void smallestFirst(int[] nums, int startIndx, int endIndx){
for(int i=startIndx; i< endIndx; i++){
if(nums[i] < nums[startIndx])
swap(nums, i, startIndx);
}
}
}
this solution will work for begining zeros, multiple simultaneous zeros, ending zero like -> {0,1,0,5,0,0,4,0,0}
package me.satyen.code;
public class Integers {
public static int rearrangeInts(int[] arr){
int cnt = -1;
int indxZ = -1;
int indxNZ = -1;
boolean foundZero = false;
for(int i=0; i< arr.length; i++){
//find first zero index first time only.
if(!foundZero && arr[i] == 0){
indxZ = i;
foundZero = true;
}else if (arr[i] != 0){ //find the non zero index
indxNZ = i;
//if we already found zero and we got non zero index then swap
//and increment zero index
if(foundZero){
swap(arr, indxZ++, indxNZ);
}
}
}
return cnt;
}
public static void swap(int[] arr, int indx1, int indx2){
int tmp = arr[indx1];
arr[indx1] = arr[indx2];
arr[indx2] = tmp;
}
public static void main(String[] args){
int[] arr = new int[]{0,1,0,5,0,0,4,0,0};
rearrangeInts(arr);
}
}
public int random75(){
int ans = random50(); // 50%
if(ans == 0){
ans = random50(); //for 0 50% / 2 = 25%
}
return ans;
}
The time complexity is O(n)
I am getting the first index of space character ' '. Once found I am reversing the word before space char.
I am assuming the string input is "the boy ran" and neglecting @
public class StringOperations {
public static void main(String[] args) {
System.out.println(reverseWords("the boy ran"));
}
/**
* Reverses sentence word by word as mentioned in problem
* @param str sentence to be reversed
* @return reversed sentence
*/
public static String reverseWords(String str) {
if (str == null) {
return str;
} else if (str.length() == 1) {
return str;
}
char[] arr = str.toCharArray();
int prevStart = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == ' ') {
//i-1 cause i is position of space
reverseArr(arr, prevStart, i - 1);
//i+1 cause we will start from char next to space char
prevStart = i + 1;
}
//if the end of sentence reached and there is no space at end
else if(i==arr.length - 1){
reverseArr(arr, prevStart, i);
}
}
return new String(arr);
}
/**
* Reverses char array between the start and end position
* @param arr array to be reversed
* @param start index where we should start
* @param end index where we should end
* @return
*/
public static char[] reverseArr(char[] arr, int start, int end) {
if (arr == null) {
return null;
} else if (arr.length == 1) {
return arr;
}
int loopTill = (end - start + 1) / 2;
for (int i = 0; i < loopTill; i++) {
//swap i and arr.length-i
char tmpChar = arr[start + i];
arr[start + i] = arr[end - i];
arr[end - i] = tmpChar;
}
return arr;
}
}
This is almost O(1) solution. Using recursion but recursive calls may be at max 3 cause maximum no=umber of columns can be 16384-> XFD.
- satyen.shimpi April 22, 2017