题解 | #删除字符串中出现次数最少的字符#

删除字符串中出现次数最少的字符

http://www.nowcoder.com/practice/05182d328eb848dda7fdd5e029a56da9

题意整理。

  • 删除字符串中出现次数最少的字符,若多个字符出现次数一样,则都删除。

方法一(Map)

1.解题思路

  • 新建一个Map,用于记录字符出现次数。
  • 遍历整个字符串,通过Map统计各个字符出现次数。
  • 然后再遍历Map,找到最小的出现次数。
  • 最后遍历字符串,如果当前字符出现次数不是最小出现次数,则加入到res。

图解展示: alt

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.复杂度分析

  • 时间复杂度:需要遍历字符串中所有字符,所以时间复杂度为O(n)O(n)
  • 空间复杂度:最坏情况下,需要额外大小为n的Map,所以空间复杂度为O(n)O(n)

方法二(利用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.复杂度分析

  • 时间复杂度:需要遍历字符串中所有字符,所以时间复杂度为O(n)O(n)
  • 空间复杂度:最坏情况下,需要额外大小为n的Map,所以空间复杂度为O(n)O(n)
xqxls的题解 文章被收录于专栏

牛客题解

全部评论
int min=20;这里为什么要设20呀?
点赞 回复 分享
发布于 2022-09-04 21:04 广东
数据范围,最大是20
点赞 回复 分享
发布于 2022-09-04 22:29 浙江

相关推荐

点赞 评论 收藏
分享
3 1 评论
分享
牛客网
牛客企业服务