The cause of

Yesterday, I scanned a LeetCode, and after successfully submitting it, I found that the execution time was still a little too long, so I beat 5% of JS users. This is no good, I have to explore and break through myself, it must be because my algorithm and writing method are too low!

The question went like this:

Leetcode title – 1170. Compare the frequency of the smallest letters in a string

Here’s my line of thought, very conventional:

  1. Write a function to calculate the frequency of the minimum letter

  2. Create an empty array answer and count variable time

  3. Double iterate through queries and words, calculate the frequency of the items of these two arrays respectively, and then compare them. If the items meet the conditions, then time+1. After traversing the inner layer, push the final count into the answer, and return answer after traversing the outer layer

Here is my code implementation:

/**
 * @param {string[]} queries
 * @param {string[]} words
 * @return {number[]}
 */
var numSmallerByFrequency = function(queries, words) {const answer = [] // Double traversal startsfor (leti = 0; i < queries.length; I ++) {// counter time is used to record the number of entries matching queries[I] and wordslet timesQueries [I] const queries_statisticsFrequency = statisticsFrequency(QUERIES [I])for (letj = 0; j < words.length; Const words_statisticsFrequency = statisticsFrequency(words[j]) {// Calculate words[j]if (queries_statisticsFrequency < words_statisticsFrequency) {
                times += 1
            }
        }
        answer.push(times)}returnanswer }; /** * this function is used to find the minimum number of letters * 1. Go through the number group, get the frequency of the minimum letter repetition, and return the frequency */ var statisticsFrequency =function (s) {

    let frenquencyObj = {}
    const arrayFromS = s.split(' ').sort()

    for(leti=0; i<arrayFromS.length; i++){ const value = frenquencyObj[arrayFromS[i]] frenquencyObj[arrayFromS[i]] = value ? Value +1:1 /** If the next letter is different from the current letter, * indicates that the minimum number of repeated letters has been accumulated, and the value */ can be returnedif(arrayFromS[i] ! == arrayFromS[i+1]){return frenquencyObj[arrayFromS[0]]
        }
    }
}
Copy the code

I submitted three times and failed twice, because some test cases exceeded the time limit. I used some scheme modification to submit the third time successfully:

  1. When converting a string to an arrays.split('')Than usingArray.from(s)More efficient.
  2. Start withArray.mapLet’s go through the loopArray.forEachAfter more efficient.
  3. useforInstead of a loopArray.forEachThis is just to optimize the algorithm, in the case of certain conditions, do not need to continue to loop, useforYou can jump out of the loop.
  4. At first it was straight in the double loopstatisticsFrequency(queries[i]) 与 statisticsFrequency(words[j])Written in the bookifStatement, causing the two values to be evaluated twice each time. And then I bring the values upifOutside of the calculation, and assign values to variables, variables to compare, also save some time.

To optimize the

How to find the minimum number of occurrences of a character in a string

/** * this function is used to find the minimum number of letters * 1. Go through the number group, get the frequency of the minimum letter repetition, and return the frequency */ var statisticsFrequency =function (s) {
    const arrayFromS = s.split(' ').sort()
    let time = 0

    for (let i = 0; i < arrayFromS.length; i++) {
        time += 1
        if(arrayFromS[i] ! == arrayFromS[i + 1]) {return time
        }
    }
}
Copy the code

With this change, we can finally beat 7.69% of JS users.

Come to think of it, why do you need an object to keep in the first place?

Using objects, you can see what the smallest character is and how many times it occurs. But this problem doesn’t really need to know what the smallest character is.

Is there a better way to do this than double traversal?

  1. First, calculate the minimum frequency of the occurrence of characters for the two array elements respectively, and store them in the new array (queriesCount / wordsCount)
  2. rightwordsCountIs sorted in descending order
  3. Try using dichotomy for traversal comparison: takequeriesCountAnd is divided again and againwordsCountTo compare
/**
 * @param {string[]} queries
 * @param {string[]} words
 * @return {number[]}
 */
var numSmallerByFrequency = function(queries, words) {const answer = [] // Calculate the frequency of the smallest characters in the queries array and store them in a new array const queriesCount = queries. Map (item => {returnStatisticsFrequency (item)}) // Count the minimum occurrences of characters in words array elements in descending order to store them in a new array const wordsCount = words.map(item => {returnStatisticsFrequency (item)}).sort(compare).reverse()let front = 0,
            end = wordsCount.length,
            mid
        while (front <= end) {

            mid = parseInt((front + end) / 2)
            
            if(mid ! == front && mid ! == end) {// dichotomyif (item >= wordsCount[mid]) {
                    end = mid
                } else{front = mid}} // When wordsCount[0] is searched, if item >= wordsCount[mid], 0 is returnedelse if(mid === 0 && item >= wordsCount[mid]) {
                answer.push(0)
                return
            }
            else{// Since mid is the index of the array, the index starts from 0, so it should return +1 answer.push(mid +1)return}}})returnanswer }; Var compare =function (a,b){
    return a-b
}
Copy the code

This is good, beat 80.77% of JS users!

extension

Note: The following code has not undergone extensive test case testing and performance testing

How do I find the most frequently occurring character in a string

Such as:

  1. The input'abfeigeaabjgeba', the result should be returneda. Explanation: BecauseaIt appears four times, and all other characters appear less than four times.
  2. The input'bfeigeaabjgeba', the result should be returnedabe. Explain becausea,b,eAll appear 3 times, and all other characters appear less than 3 times.

The code implementation is as follows:

var maxTimeCharacter = function (s) {
    let frenquencyObj = {},
        maxTime = 0,
        character = ' '
    const arrayFromS = s.split(' ').sort() arrayfroms.foreach (item => {// treat characters as keys and occurrences as valueslet value = frenquencyObj[item]
        frenquencyObj[item] = value ? (++value) : 1

        if (maxTime <= value) {
            maxTime = value
            if(character ! == item) { character += item }else {
                character = item
            }
        }
    })
    return character
}
Copy the code

How to find the smallest character in a string that occurs more than 1 times

Such as:

  1. The input'abfeigeaabjgeba', the result should be returneda. Explanation: BecauseaIt appears four times, and all other characters appear less than four times.
  2. The input'bfeigeaabjgeba', the result should be returneda. Explain becausea,b,eAll the other characters are less than 3 times, butaThe character is the smallest character

The code implementation is as follows:

var moreTimeCharacter = function (s) {
    let frenquencyObj = {},
        maxTime = 0,
        character = ' '
    const arrayFromS = s.split(' ').sort() arrayfroms.foreach (item => {// treat characters as keys and occurrences as valueslet value = frenquencyObj[item]
        frenquencyObj[item] = value ? (++value) : 1

        if (maxTime <= value) {
            maxTime = value
            if(character ! == item) { character += item }else {
                character = item
            }
        }
    })
    return character.charAt(0)
}
Copy the code