Leetcode1170- compare the occurrence frequency of the minimum letter of the string (the corresponding occurrence frequency of each string minimum element in the map set storage array)

Catalog

1. subject ：

2. analysis ：

3. Ideas ：

4. Code implementation ：

---

1. subject ：

2. analysis ：

      Analyze the meaning of the topic ,queries Every word in the needs and words Compare all the words in , The frequency of each word is the number of words with the lowest frequency and words Compare the minimum number of occurrences of each word in , The statistical frequency is less than words The frequency of occurrence of the smallest letter of a word in （ Every queries[i] Count it once , The results of each time are put into , Returns an array of ）.

3. Ideas ：

1. Statistical string array words The minimum occurrence frequency of words in each string is put into map A collection of val

2. Traverse queries, Get the occurrence frequency of the minimum word of each string q. At the same time, set the inner loop traversal map Collection fetch times val and q The comparison ,q<val Then count the times , The number of times after the inner loop is completed is put into the array , Carry out the next external circulation ...... Until the loop is traversed , Returns an array of .

3. Refining operation ： Finding the frequency of the smallest word in the string can be put in a single method , Two methods ：1> You can find the smallest word by cycling first , Count the number of times ;2> Count the times while looking

4. Code implementation ：

/**
 *  Here are two string arrays to look up queries And vocabulary words
 *  For each query queries[i] , Statistics required words Meet in f(queries[i])< f(W) The number of words used ,W Represents a vocabulary words Every word in .
 *  Please return an integer array answer As the answer , Each of them answer[i] It's No i Results of this query 
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *  analysis ： namely queries Every word in the needs and words Compare all the words in , The frequency of each word is the number of words with the lowest frequency and words Compare the minimum number of occurrences of each word in 
 *  Statistics less than words The number of words in （ Every queries Count it once ）
 *  Ideas ：
 * 1.map Collective storage words Index of each string in (key) And the frequency of the smallest word in the corresponding string （val）
 * 2. Double traversal , External traversal queries This string array , Inner layer traversal takes map value 
 *  .queries The minimum word frequency of each string is the same as val compare , If less than val Then count the number of times , Inner layer map After traversal, count the number of times to the array 
 * 3. Find the smallest character in the string （ Small letters ） Occurrence times alone as a method ：
 *   1> You can find the smallest word by cycling first , Count the number of times 
 *   2> Count the times while looking 
 */
public class Num1170_NumSmallerByFrequency {
    public  int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] res=new int[queries.length];
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            int count=findMin(words[i]);// The minimum number of characters in the current string 
            map.put(i,count);
        }
        // here words All the contents in map It's in the assembly , Traverse queries Array of strings 
        // Outer loop traversal queries Each string in queries[i]
        for (int i = 0; i < queries.length ; i++) {
            // The inner loop traverses again map Set for frequency comparison 
            int q=findMin(queries[i]);// To calculate the queries[i] If times 
            int num=0;// Record queries...<words... Frequency of 
            for(int key:map.keySet()){//map.keySet(): obtain key value 
                if(q<map.get(key)){
                    num++;
                }
            }
            res[i]=num;
        }
        return res;
    }

    /**
     *  2> Count the number of times while finding the smallest word 
     */
    private  int findMin(String str){
        char[] array=str.toCharArray();
        char ch=array[0];
        int count=1;
        for (int i = 1; i < array.length; i++) {
            if(array[i]==ch){
                count++;
            }else if(array[i]<ch){
                //i The index position value is small 
                ch=array[i];
                count=1;
            }//i The value at the large index is large, and it is directly traversed backwards without processing 
        }
        return count;
    }
    /**
     * 1> You can find the smallest word by cycling first , Count the number of times 
     */
//    private  int findMin(String str) {
        char ch=str.charAt(0);// Get the first letter 
        for (int i = 1; i < str.length(); i++) {// Traverse to find the smallest letter 
            if(str.charAt(i)<ch){
                ch=str.charAt(i);
            }
        }
//        /**
//         *  It can be written as above , But it's best to convert it directly into a character array , Easy to use 
//         */
//        char[] array=str.toCharArray();// String to array 
//        char ch=array[0];
//        for (int i = 1; i < array.length; i++) {// Traverse to find the smallest character 
//            if(array[i]<ch){
//                ch=array[i];
//            }
//        }
//        // Come here ch Is the smallest letter , Count the number of times the minimum letter is traversed again 
//        int count=0;
//        for (char i :array) {
//            if(i==ch){
//                count++;
//            }
//        }
//        return count;
//    }
}