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

一时失言乱红尘 2023-07-01 08:33 22阅读 0赞

[https://www.nowcoder.com/practice/05182d328eb848dda7fdd5e029a56da9?tpId=37&tqId=21246&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking][https_www.nowcoder.com_practice_05182d328eb848dda7fdd5e029a56da9_tpId_37_tqId_21246_tPage_2_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]

## 一、题目描述 ##

实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。

## 二、代码实现 ##

使用哈希表：

import java.util.Iterator;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Set;
    public class Main {
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    		
    		while (sc.hasNext()) {
    			String input = sc.next();
    			HashMap<Character, Integer> map = new HashMap<>();
    			for (int i=0; i<input.length(); i++) {
    				char ch = input.charAt(i);
    				if (map.get(ch) == null) {
    					map.put(ch, 1);
    				} else {
    					map.put(ch, map.get(ch)+1);
    				}
    			}
    			
    			int min = Integer.MAX_VALUE; //int min = Collections.min(map);
    			int max = Integer.MIN_VALUE;
    			for (Map.Entry<Character, Integer> entity : map.entrySet()) {
    				if (entity.getValue() < min) {
    					min = entity.getValue();
    				}
    				if (entity.getValue() > max) {
    					max = entity.getValue();
    				}
    			}
    			
    			String result = "";
    			if (max == min) {
    				result = input;
    				System.out.println(result);
    				continue;
    			}
    			StringBuilder sb = new StringBuilder();
    			for (int i=0; i<input.length(); i++) {        //由于需要保持原有相对次序，所以这里遍历的还是原始字符串
    				char ch = input.charAt(i);
    				int count = map.get(ch);
    				if (map.get(ch)!=null && count!=min) {
    					sb.append(ch);
    				}
    			}
    			result = sb.toString();
    			System.out.println(result);	
    		}
            
        }
    }

采用计数排序/桶排序的思想：

import java.util.Scanner;
    import java.util.Arrays;
    public class Main {
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int[] flags = new int[26];
            
            while (sc.hasNext()) {
                Arrays.fill(flags, 0);
                String input = sc.next();
                if (input.length() == 0) {
                    continue;
                }
                
                for (int i=0; i<input.length(); i++) {
                    flags[input.charAt(i)-'a']++;
                }
                
                //int min = 0;    //input.length() >= 1
                int min = Integer.MAX_VALUE;
                for (int i=0; i<flags.length; i++) {
                    //if (flags[i] <= flags[min]) {
                    //swumneiiii  输出swumneiiii  期待iiii
                    //
                    if (flags[i] != 0 && flags[i] < min) {    //注意这里出现次数为0的字符不能考虑在内
                        min = flags[i];
                    }
                }
                
                for (int i=0; i<input.length(); i++) {
                    if (flags[input.charAt(i)-'a'] != min) {
                        System.out.print(input.charAt(i));
                    }
                }
                //不加上这一句会报错，可能是平台原因
                System.out.println();
            }
        }
    }

[https_www.nowcoder.com_practice_05182d328eb848dda7fdd5e029a56da9_tpId_37_tqId_21246_tPage_2_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]: https://www.nowcoder.com/practice/05182d328eb848dda7fdd5e029a56da9?tpId=37&tqId=21246&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking