只需提供思路 谢谢!!!!
Description
输入由{'o','r','z'}组成的字符系列对其按字母顺序排序。
如果规定排序过程只能做交换工作来达到排序效果(类似冒泡排序)。
求最小交换次数。
Input
一个整数T,表示测试数据个数。
每个测试数据包含一个数字n(字符个数,不计空格),0<n<10000 和字符序列str。
Output
最小交换次数。
Sample Input
3 3 z ro 2 z r 5 o orr z
Sample Output
1 1 0
Hint
Hint:
字符序列
z,r,o
排完序后为
o,r,z
所以只要交换z,o
即1 次就能达到排序效果
import java.util.Scanner;
public class OrzSort {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String strTemp = sc.nextLine();
String[] strStr = strTemp.split(" ");
for(int cc=2;cc<strStr.length;cc+=2){
char[] str =strStr[cc].toCharArray();
int count=0;
for(int i=0,j=str.length;i<j;i++){
if(str[i]!='o'){
for(int k=str.length-1;k>i;k--){
if(str[i]>str[k]){
count++;
char temp=str[i];
str[i]=str[k];
str[k]=temp;
}
}
}
}
System.out.println(count);
}
}
}
可以按你的要求输入了,输在一行上,以空格隔开就可以了
首先有一个输入,然后对输入的内容就是3 3 zro 2 z r 5 oorrz 进行解码,把解码后的内容放到一个数组或者集合里,然后用这些数据做准备。
把解码得到的数据按照组来做排序,确定每组的排序次数。
具体排序,我的思路是这样的
为简化理解我用abcde来解释
有一个序列为adcbe则要进行一次排序,原因是只需要交换db,而又有一个序列acdeb则要进行3次,即b<->c
,c<->d,d<->e。有什么规律呢,你有没有发现在第一个例子中有三个字母是不用动的。在第二个中a也是不用动的,这样我们就可以来这么想,我们把这几个字母分为稳定与非稳定字母,不用动的就叫它稳定字母。
然后统计每个字母是不是稳定的,那接下来问题是怎么就是稳定的了呢。我们可以为每个字母设置一个属性,用来记录该字母在这个串里的位置,比如a就是1,b就是2依次类推(相同字母如aabbc可以把第一个a设为1,第二个设为2,依次)。然后把该属性跟自己的索引值相比较,就知道其是否稳定了。
接下来就好办多了,你再看看不稳定的字母序列的排序,你会发现这样的规律,比如,2个不稳定字母,ba只要一次排序,3个bca要两次,4个三次,依次,这样就找到了规律,就是n-1.到此,问题解决。
用时15分钟,希望采纳,谢谢