给大家出个题目吧，朋友面试某外企的。

Question

把一个字符串中大写字母排列到前面，小写字母排列到后面。
就干这个，NOTICE，不需要排序，也别整Set那些玩意，显得低能。"HiHelloWorld" ==> "HHWielloorld";

Answer 1

不，是Show me the code, 我要O（n*log(n)）t以下的，我也不要有更高的空间复杂度。

Answer 2

public static void main(String[] rags) 
{
  String str = "HiHelloWorld";
  char[] ch = str.toCharArray();
  StringBuffer sbB = new StringBuffer();
  StringBuffer sbS = new StringBuffer();
  for(char c : ch)
  {
    if(c<='a')
    {
      sbB.append(c);
    }
    else
    {
      sbS.append(c);
    }
  }
  str = sbB.append(sbS.toString()).toString();
  System.out.println(str);
}笨是笨了点,勉强实现了喵~~``

Answer 3

复杂度已经不记得怎么算了
晚上回去看看去
    public void ttt() {
        String str = "Hello World";
        StringBuffer sb = new StringBuffer(str);
        char[] ch = str.toCharArray();
        int pos = 0;
        for (int i=0;i<ch.length;i++) {
            if (Character.isLowerCase(ch[i])) {
                sb.deleteCharAt(pos);
                sb.append(ch[i]);
            } else if (Character.isUpperCase(ch[i])) {
                pos ++;
            } else {
                sb.deleteCharAt(pos);
            }
        }
        System.out.println(str);
        System.out.println(sb.toString());
    }

Answer 4

嗯 一个循环0(n)把大小写都拣出来放两篓子里 我也类似这样做的         String input = "HiHelloWorld";
        char[] myChar = input.toCharArray();        int length = input.length();
        char[] upperChar = new char[length];
        char[] lowerChar = new char[length];
        int upperIndex = 0, lowerIndex = 0;
        for (int i = 0; i < length; i++) {
            if (Character.isUpperCase(myChar[i])) {
                upperChar[upperIndex++] = myChar[i];
            }
            else {
                lowerChar[lowerIndex++] = myChar[i];
            }
        }        for (int i = 0; i < upperIndex; i++) {
            myChar[i] = upperChar[i];
        }        for (int i = 0; i < lowerIndex; i++) {
            myChar[upperIndex++] = lowerChar[i];
        }
        
        String result = new String(myChar);
        System.out.println(result);

Answer 5

public class asdf
{
public static void main(String[] args)
{
System.out.println("HiHelloWorld ==>  HHWielloorld"; );
}
}

Answer 6

写了个比较傻的，不能有其他字符，我不会算算法效率。public class Test {    public static void main(String[] args) {
        String str = "HiHelloWorld";
        char[] c = str.toCharArray();
        char[] s = new char[c.length];
        int left = 0;
        int right = c.length - 1;        
        for(int i = 0, k = c.length; i < k; i++) {
            if(c[i] >= 'A' && c[i] <= 'Z') {
                s[left++] = c[i];
            }
            if(c[k - 1 - i] >= 'a' && c[k - 1 - i] <= 'z') {                
                s[right--] = c[k - 1 - i];
            }
        }
        String ss = new String(s);
        System.out.println(ss);
    }
}

Answer 7

set啥的不能用 那String的insert append delete能用不
用个算是原始的方法 不会算时间复杂度 不过我想这个复杂度肯定超出楼主的要求了 重在参与 呵呵public class Test{
public static void main(String args[]){
String str="HiHelJloWorld";
char temp;
int k=0;
char[] c=str.toCharArray();
for(int i=0;i<c.length;i++){
if(c[i]>='A'&c[i]<='Z'){
temp=c[i];
for(int j=i;j>k;j--){
c[j]=c[j-1];
}
c[k++]=temp;
}
}
System.out.print(c);
}
}

Answer 8

用数据结构行不??
用StringBuffer去装那个字符串,小写字母入队列,留下大写字母后面加上队列里面的所有小写字母

Answer 9

我也不要有更高的空间复杂度
=============================
这句话什么意思?除了原有STRING以外不许再用别的空间了?

Answer 10

public class TEST { public static void main(String[] args) {
String str = "HiHelloWorld";
String str2 = str.replaceAll("[a-z]","");
String str3 = str.replaceAll("[A-Z]","");
System.out.println(str2 + str3);
}}
//输出结果
HHWielloorld
满足了吗？

Answer 11

结果: HHJWielloorld，我这个效率也不高呀
import java.util.*;
public class Test { public static void main(String[] args) {
Stack<String> stk = new Stack<String>();
String s="HiHelJloWorld";
String sL = "";
String sU = "";
String result = "";
char[] c = s.toCharArray();
for(int i = 0; i < c.length; i++) {
if(c[i] >= 'a' && c[i] <= 'z')
sL += c[i];
else
sU += c[i];
}
stk.push(sL);
stk.push(sU);

while(!stk.isEmpty()) {
result += stk.pop();
}

System.out.println(result);
}}

Answer 12

merge...
满足:
把一个字符串中大写字母排列到前面，小写字母排列到后面。
就干这个，NOTICE，不需要排序，也别整Set那些玩意，显得低能。不过不满足:
"HiHelloWorld" ==>  "HHWielloorld"; ==
code:
public class TestMain {
public static void main(String [] args){
TestMain tm = new TestMain();
tm.swapStr();
}

private void swapStr(){
String str = "HiHelloWorld";
char [] c = str.toCharArray();
int max = str.length()-1;
int start = 0;
int end = max;
while (start < end){
while(c[start]>= 'A' && c[start]<='Z'){
start++;
}
while (c[end]>= 'a' && c[end] <= 'z'){
end--;
}
if (start<end){
char tmp = c[start];
c[start] = c[end];
c[end] = tmp;
}
}
String out = new String(c);
System.out.println(out);
}
}

Answer 13

如果不要求出来的字符串的顺序  那只是简单的找到相应的 然后swap public static String method1(String s)
{
char[] chars = s.toCharArray();

for(int i = 0; i < chars.length; i++)
{
char lowercase = chars[i];
if( lowercase >= 97 && lowercase <= 122 )
{
for(int j = i; j < chars.length; j++)
{
char capital = chars[j];

if(capital >= 65 && capital <= 90)
{
chars[i] = capital;
chars[j] = lowercase;
break;
}
}
}
}


return new String(chars);
}

Answer 14

我的C源码:
#include <stdio.h>
#define UPPERCASE(c) (c>='A'&&c<='Z') 
#define LOWERCASE(c) (c>='a'&&c<='z')
main()
{
char str[]="HiHelloWorld";
int i=0,start=0,end=0;
/*计算字符串长度*/
while(str[i++]!='\0')
end++;
end--;
while(start!=end)
{
if(UPPERCASE(str[start])&&LOWERCASE(str[end]))
start++,end--;
else if(UPPERCASE(str[start])&&UPPERCASE(str[end]))
start++;
else if(LOWERCASE(str[start])&&LOWERCASE(str[end]))
end--;
else
{
char cTemp;
cTemp=str[start];
str[start++]=str[end];
str[end--]=cTemp;
}
}
i=0;
while(str[i]!='\0')
{
printf("%c",str[i++]);
}
putchar('\n');
}

Answer 15

首先StringBuffer，里面维护了一个定长的数组，当append超过了这个长度后，会出现内存的重新分配，和内存拷贝。
用String就更离谱了，String的+=是一个多么耗费的过程啊。
诸位，算法不是为了看着好看的，要追求好的，合理的时间，空间复杂度。
你们可以把这个问题发到.Net版，和C++版，你看看他们会给出什么样的答案？
这个题目最佳的结果是不需要开辟一个Buffer，也不需要两层的循环，只要在一个数组之内就可以完成了。
我都提示到这个份上了

Answer 16

33楼，没有看你的代码哦，写完后才发现这么相似。
同样所有的条件都满足，算法时间效率和空间效率都为O(n)，只有"HiHelloWorld" ==>   "HHWielloorld"不满足，如果非得变成这样，只有增加辅助空间了，但也不会超O(nlogn)。只需在交换时将小写字母保存到数组中，循环结束后，再统一将小写字母插入即可。
修改后的算法均符合楼主的要求。

Answer 17

只有33楼的接近我的要求，但是还是慢了很多，唉。 
======
其实, 我并不大懂java,用的只是数据结构中排序常用的 merge, 算法复杂度 时间:O(n),空间 O(n+1). :) qzmguy:
呵呵, 想法一样,这个还是比较常见的 :)

Answer 18

C/C++:16355分 扩充话题:9331分 Java:8120分            甘草得分....
终于明白了....

Answer 19

把 swap优化一下可以 , 不用多余空间

Answer 20

        String str = "HiHelloWorld";
        char[] c = str.toCharArray();
        int max = str.length() - 1;
        int start = 0;
        int end = max;
        while (start < end) {
            
            if(c[start] > c[end] && c[start] >= 'a' && c[end] <= 'Z') {
                char tmp = c[start];
                c[start] = c[end];
                c[end] = tmp;
                start++;
                end--;
            } else if(c[start] <= 'Z'){
                start++;
            } else if(c[end] >= 'a') {
                end--;
            }        }
        System.out.println(c);
改了下33楼的 貌似不需要多while 首尾交换 一个char[]

Answer 21

时间:O(2n),空间 O(2n).  可以实现 

Answer 22

str[start]=str[sstart]+str[end];
str[end]=str[start]-str[end];
str[start]=str[start++]-str[end--];
这总行了吧，典型的用时间换空间啊

Answer 23

38楼的代码如果运行成功的，想必是最高效的，看到了嘛？这个是一个C代码，但是快并非因为他是用C写的，而是他的逻辑表达和思想是正确的。这个题目理论上只要一层循环，和这个数组本身。在内部进行交换足矣。
字符串长度如果是N，那么循环的次数应该大概就是N的。里面大概会出现一次判断和一次交换。这个就是效率。
PS:
可以找找Greta正则的实现看看，或者Python，Ruby的源码，里面都有正则的实现。
也应该知道StringBuffer的结构和工作原理。

Answer 24

嗯，我打算把分涨到100，都给qzmguy。
而且你也很自信，我不用编译你的代码了。

Answer 25

不愧是外企的题，下班后好好研究一下。不过楼主是不是部要求排列前的顺序跟排列后相同阿
如果是的话，可以用循环加二分发把for i 0-〉字符数组长(O(n)) {
  if i处字符是小写 {
    二分法查大写字母(O(logn))
    交换字母
  }
}

Answer 26

就是去Baidu的题目。呵呵。

Answer 27

不行，楼上的结果有误，iHHelloWorldA 就不对了，应输出：HHWAielloorld，但输出的是：AHHWlloeorldi

Answer 28

始终觉得学JAVA是为了方便....
恩,不敢驳甘草的意思...只是...C的话我一定也是这么写,因为我没办法
JAVA我一定不这么写,因为我想偷懒

Answer 29

其实这类题目还可以再变一下，比如字符串是由大写字母，小写字母，数字组成，如"HiHelloWorld520"，要求大写字母放前面，数字放中间，小写字母放后面。同样要求在O(n)内完成。

Answer 30

看了38楼的代码了
我觉得如果从后边向前推进找大写字符不如用二分法在剩下的（start之后的）字串里找快。
不知道大家什么感觉。

Answer 31

貌似我回的没回成功啊
恩,怎么说呢,我学JAVA始终是为了方便
恩...不敢驳甘草的意思
但是如果是用C的话,当然我还会点.我也会用数组去实现,因为我不知道其他办法了
但是如果是JAVA,我一定不用数组实现,毕竟用其他方法至少在写代码的人而言方便了很多,看的人也方便很多
在数组中的穿梭始终有些个不烦琐

Answer 32

qzmguy:
呵呵, 你说得对,其实这样是降低效率...考智力题才会这么做,真的项目开发,我想没有人会这么做.

Answer 33

我的想法是避免使用method可能會快些
public static void main(String[] args) {
        char[] charAry = {'H','i','H','e','l','l','o','W','o','r','l','d'};//打好久
        String str = "" ;
        int index = 0 ;        
        while(index < charAry.length){
            if((int)charAry[index] < 91) //ascii Z=90
                System.out.print(charAry[index++]);
            else
                str += charAry[index++] ;
        }
        System.out.print(str);//剩下小寫的字            
    }

Answer 34

不排序的意思 就是 AbcD的 结果可以是ADbc  或者 是 ADcb  ?

Answer 35

甘草，我好像没有这个权限给你加分吧。再者说，38楼的结果是错的。测试数据：iHHelloWorldA
条件：把一个字符串中大写字母排列到前面，小写字母排列到后面。
结果应是：HHWAielloorld但是38楼的结果是：AHHWlloeorldi根据不符合题意的要求！“i”是第一个出现的，应在小写字母的第一个，我想应该不是最后一个吧。

Answer 36

public static void main(String[] args) {
        hh hh = new hh();
        char []a=new char[hh.m.length()];
        StringBuffer sb=new StringBuffer();
        StringBuffer sp=new StringBuffer();
        String jieguo=new String();
        for (int i = 0; i < hh.m.length(); i++) {
           a[i]= hh.m.charAt(i);
           if (Character.isUpperCase(a[i])) {
               sb.append(a[i]);
           }
           else{
           sp.append(a[i]);
           }
        }
        jieguo=sb.toString()+sp.toString();
        System.out.println(jieguo);
    }}
5楼加3楼就是这样，我不知道比用StringBuffer 更简洁的方法
attention!!!

Answer 37

qzmguy:
呵呵, 你说得对,其实这样是降低效率...考智力题才会这么做,真的项目开发,我想没有人会这么做.
___________________________________________________________________________________________
在数据量小的时候，往往不察觉。
有些代码看似和qz的很相似了，你干吗不在循环那里用个变量记录循环的次数呢？
你会发现你们的代码的循环次数可以用天壤之别来形容。你们看到了count后，就会真切地体会到n和n^2,和n*log(n)的差别了。

Answer 38

没写代码，但是我的想法是  取字母的 ascll码 然后 按大小走

Answer 39

不排序，就是不排序，这个是原题，你管i到哪里去那，大写小写前后分开就是结果。
还有那个StringBuffer的，要我说多少遍？简洁的代码参加洁癖家庭妇女代码大赛去。我只要效率，时间，空间。

Answer 40

...
java不能成为追求效率极致的障碍和借口
实际条件和时间允许的话 尽量往人为最大化方向靠喽 

Answer 41

怎么可能没说呢示例是："HiHelloWorld" ==>  "HHWielloorld"，这个就是按原序排的。结果不是：WHHdlroolli 这样子的（因为不考虑顺序这个也是正确的，但是这样的结果会有 N 种，
我认为这种根本不符合题意）。

Answer 42

qzmguy:
呵呵, 你说得对,其实这样是降低效率...考智力题才会这么做,真的项目开发,我想没有人会这么做.
___________________________________________________________________________________________
在数据量小的时候，往往不察觉。
有些代码看似和qz的很相似了，你干吗不在循环那里用个变量记录循环的次数呢？
你会发现你们的代码的循环次数可以用天壤之别来形容。你们看到了count后，就会真切地体会到n和n^2,和n*log(n)的差别了。 
===我的算法nlog(n)以上?仔细看一下吧 :) 

Answer 43

public static void main(String[] rags) 
{
  String str = "HiHelloWorld";
  int sizeB=0;
  char[] ch = str.toCharArray();
  int[] inB = new int[ch.length+1];
  for(int i=0;i<ch.length;i++)
  {
    if(ch[i]<='a')
    {
      inB[sizeB] = i;
      sizeB++;
    }
  }

  for(int i=0;i<sizeB;i++)
  {
    if(i!=inB[i])
    {
      char ex = ch[i];
      ch[i]=ch[inB[i]];
      ch[inB[i]]=ex;
    }
  }
  System.out.println(String.valueOf(ch));
}
又改了下,这个时间上好了点,不过空间需要一个记录大写字母编号的数组,而且小写字母顺序变了喵~~`

Answer 44

public static void main(String[] rags) 
{
  String str = "HiHelloWorld";
  int sizeB=0;
  char[] ch = str.toCharArray();
  int[] inB = new int[ch.length+1];
  for(int i=0;i <ch.length;i++)
  {
    if(ch[i] <='a')
    {
      inB[sizeB] = i;
      sizeB++;
    }
  }  for(int i=0;i <sizeB;i++)
  {
    if(i!=inB[i])
    {
      char ex = ch[i];
      ch[i]=ch[inB[i]];
      ch[inB[i]]=ex;
    }
  }
  System.out.println(String.valueOf(ch));
} 
忘记加框了喵~~`

Answer 45

哎，白想了
"HiHelloWorld" ==>  "HHWielloorld"; 
这还不是坑人么？
否则一个划分算法不是完了么？但却没办法出这个结果

Answer 46

看了這么多
我搞笑幾吧
你說無所謂順序
那直接random他   運氣好的話就是大寫在前小寫在后，速度又夠快
當然，那要你rp好才行。
==========
按你的題目的話我覺得還是30樓好
我是按我的角度來說的，代碼少，看得懂，符合java的思想
畢竟你題目里又沒說要求效率

Answer 47

哈哈 不排序
"HiHelloWorld" ==>"HHWielloorld"; 这个完全是误导 
你说是"HiHelloWorld" ==>"HWHielorldlo";你要的答案早就有了 

Answer 48

我也过来玩玩
#include<iostream>
using namespace std;
bool insertFront(char* p,int size, int idx1, int idx2)
{
if(idx1>size-1 || idx2>size-1 || idx2<idx1)
return false;
char a=*(p+idx2);
for(int i=idx2; i>idx1; i--)
{
*(p+i)=*(p+i-1); }
*(p+idx1)=a; return true;
}
int main()
{
char test[]={"HiHelloWorld"};
char tmp;
int n=0; for(int i=0; i<sizeof(test)-1; i++)
{
if(*(test+i)<'a')
{
tmp=*(test+i);
*(test+i)=*(test+n);
*(test+n)=tmp;
insertFront(test,sizeof(test),n+1,i);
n++; } }
cout<<test<<endl;
return 0;
}

Answer 49

TO Qh，对不起，你的代码我没有细看，但是单看你一个循环里面套着两个循环，我觉得效率就不可能太好了。
完成题意只要一个循环，而且次数不会超过字符串的长度。
Java版平时都是很讲效率和算法的嘛，不要一到做题的时候又来扯可读性。
就这样，看懂38楼的代码吧。

Answer 50

不管顺序的话public class Test{
    public static void main(String args[]){
        String str="HiHelJloWorld";
        char temp;
        int k=0;
        char[] c=str.toCharArray();
        for(int i=0;i<c.length;i++){
            if(c[i]>='A'&c[i]<='Z'){
                temp=c[k];
                c[k]=c[i];
                c[i]=temp;
                k++;
            }
        }
        System.out.print(c);
    }
}
这样不是很简单吗

Answer 51

看我的双枪老太，分别从两端扫描：
public class Test {    public static void main(String[] args) throws Exception {
        String str = "HiHelloWorld";
        final int length = str.length();        char temp[] = new char[length];
        int front = 0;
        int back = length - 1;
        for (int i = 0; i < length - i; ++i) {
            if (Character.isLowerCase(str.charAt(i))) {
                temp[back--] = str.charAt(i);
            } else {
                temp[front++] = str.charAt(i);
            }            if (Character.isLowerCase(str.charAt(length - i - 1))) {
                temp[back--] = str.charAt(length - i - 1);
            } else {
                temp[front++] = str.charAt(length - i - 1);
            }
        }
        str = new String(temp);
        
        System.out.println(str);
    }
}