同學給我發的一個筆試題:
給定1到n的一個子序列,每次隻能翻轉裡面的一個子數組,問最少需要幾次翻轉可以使得數組升序排列?
簡單概括就是:翻轉子數組的方法給數組排序;
思路挺簡單的,随便寫了一個,可以一起讨論哈哈
package com.baorant;
import java.util.Scanner;
/*
* 翻轉子數組給數組排序
*/
public class TranceDemo {
public static void main(String[] args) {
// //測試翻轉函數
// int[] a ={1,3,4,5};
// int[] b = changePart(a, 1, 3);
// System.out.println("測試翻轉函數:");
// for(int i = 0; i < b.length; i++){
// System.out.print(b[i] + " ");
// }
// System.out.println();
Scanner sc = new Scanner(System.in);
int number = sc.nextInt();
int[] nums = new int[number];
for(int i = 0; i < number; i++){
nums[i] = sc.nextInt();
}
int count = sortByChangePart(nums);
System.out.println(count);
}
//翻轉子數組
public static int[] changePart(int[] nums, int begin, int end){
int total = begin + end;
for(int i = begin; i < (begin + end)/2 + 1; i++){
int tem = nums[i];
nums[i] = nums[total - i];
nums[total - i] = tem;
}
return nums;
}
//擷取子數組最小值所在下标
public static int minPosition(int[] nums, int begin, int end){
int min = nums[begin];
int minPoint = begin;
for(int i = begin; i < end + 1; i++){
if(nums[i] < min){
min = nums[i];
minPoint = i;
}
}
return minPoint;
}
//擷取子數組最大值所在下标
public static int maxPosition(int[] nums, int begin, int end){
int max = nums[begin];
int maxPoint = begin;
for(int i = begin; i < end + 1; i++){
if(nums[i] > max){
max = nums[i];
maxPoint = i;
}
}
return maxPoint;
}
//翻轉子數組的方式給數組排序
public static int sortByChangePart(int[] nums){
int count = 0;
int begin = 0;
int end = nums.length - 1;
while(begin < end){
//找到最小值點,到起點位置進行翻轉;
int minPoint = minPosition(nums, begin, end);
if(minPoint != begin){
changePart(nums, begin, minPoint);
count++;
begin++;
}
//找到最大值點,到終點位置進行翻轉;
int maxPoint = maxPosition(nums, begin, end);
if(maxPoint != end){
changePart(nums, maxPoint, end);
count++;
end--;
}
}
return count;
}
}