题解 | #删除字符串中出现次数最少的字符#
删除字符串中出现次数最少的字符
http://www.nowcoder.com/practice/05182d328eb848dda7fdd5e029a56da9
题意整理。
- 删除字符串中出现次数最少的字符,若多个字符出现次数一样,则都删除。
方法一(Map)
1.解题思路
- 新建一个Map,用于记录字符出现次数。
- 遍历整个字符串,通过Map统计各个字符出现次数。
- 然后再遍历Map,找到最小的出现次数。
- 最后遍历字符串,如果当前字符出现次数不是最小出现次数,则加入到res。
图解展示:
2.代码实现
import java.util.Scanner;
import java.util.HashMap;
public class Main{
public static void main(String[] args){
//标准输入
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
//用于记录字符出现次数
HashMap<Character,Integer> map=new HashMap<>();
String s=sc.nextLine();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
//如果不包含,设定次数为1
if(!map.containsKey(c)){
map.put(c,1);
}
//如果包含,在原来次数基础上加1
else{
map.put(c,map.get(c)+1);
}
}
//用于计算最小出现次数
int min=20;
for(char c:map.keySet()){
min=Math.min(min,map.get(c));
}
//记录删除出现次数最少字符后的字符串
StringBuilder res=new StringBuilder();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(map.get(c)!=min){
res.append(c);
}
}
System.out.println(res.toString());
}
}
}
3.复杂度分析
- 时间复杂度:需要遍历字符串中所有字符,所以时间复杂度为。
- 空间复杂度:最坏情况下,需要额外大小为n的Map,所以空间复杂度为。
方法二(利用io操作)
1.解题思路
与方法一的思路基本一致,不过使用io操作来处理输入数据。
2.代码实现
import java.io.*;
import java.util.HashMap;
public class Main{
public static void main(String[] args) throws Exception{
//io操作处理输入
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
while((s=br.readLine())!=null){
//用于记录字符出现次数
HashMap<Character,Integer> map=new HashMap<>();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
//如果不包含,设定次数为1
if(!map.containsKey(c)){
map.put(c,1);
}
//如果包含,在原来次数基础上加1
else{
map.put(c,map.get(c)+1);
}
}
//用于计算最小出现次数
int min=20;
for(char c:map.keySet()){
min=Math.min(min,map.get(c));
}
//记录删除出现次数最少字符后的字符串
StringBuilder res=new StringBuilder();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(map.get(c)!=min){
res.append(c);
}
}
System.out.println(res.toString());
}
}
}
3.复杂度分析
- 时间复杂度:需要遍历字符串中所有字符,所以时间复杂度为。
- 空间复杂度:最坏情况下,需要额外大小为n的Map,所以空间复杂度为。
xqxls的题解 文章被收录于专栏
牛客题解