/*
approach: 1) Greedily find maximum element and flip it to top
2) Flip top element so that it moves at the bottom of stack
...repeat until sorted
Time : O(n^2) //findMax-> O(n) * flip-> O(n) , on each iteration
Space: O(n) //if temporary swap variable is counted
O(1) //else
*/
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter bw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
String line;
int[] numbers = new int[35];
int nn;
while ((line = br.readLine()) != null) {
nn = 0;
String[] parts = line.split(" ");
for (String part : parts) {
int num = Integer.parseInt(part);
numbers[nn++] = num;
}
//process numbers,nn here
bw.printf("%s%n",line);
prefixReversalSort(numbers, nn, bw);
}
bw.flush();
br.close();
bw.close();
}catch(Exception ex){System.exit(0);}
}
public static void prefixReversalSort(int[] arr, int len, PrintWriter bw) {
for (int i = len - 1; i > 0; i--) {
int maxIndex = findMax(arr, i);
//already at correct position
if(maxIndex != i){
//already at top
if(maxIndex != 0){
bw.printf("%d ",(len - maxIndex));
flip(arr, maxIndex);
}
bw.printf("%d ",(len - i));
flip(arr, i);
}
}
bw.println("0");
}
public static int findMax(int[] arr, int end) {
int maxIndex = 0;
for (int i = 1; i <= end; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
public static void flip(int[] arr, int end) {
int i = 0;
int j = end;
while (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
}
Similar problem: Leetcode 969 : Pancake Sorting
import java.io.*;
import java.util.*;
public class Solution {
public List<Integer> pancakeSort(int[] arr) {
List<Integer> out = null;
out = new ArrayList<Integer>();
int len = arr.length;
for (int i = len - 1; i > 0; i--) {
int maxIndex = findMax(arr, i);
//already at correct position
if(maxIndex != i){
//already at top
if(maxIndex != 0){
out.add(maxIndex+1);
flip(arr, maxIndex);
}
out.add(i+1);
flip(arr, i);
}
}
return out;
}
public int findMax(int[] arr, int end) {
int maxIndex = 0;
for (int i = 1; i <= end; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
public void flip(int[] arr, int end) {
int i = 0;
int j = end;
while (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
}
No comments:
Post a Comment