Пронађите решење Леетцоде решење


Ниво тешкоће Лако
Често питани у адобе амазонка гоогле
Хасхинг низ

У овом проблему су нам дата два струне. Други низ се генерише случајним премештањем знакова првог низа, а затим додавањем додатног знака на било којој случајној позицији. Морамо вратити додатни знак који је додан другом низу. Знакови ће увек бити мала енглеска слова.

Пример

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

Објашњење # 1

Додатни знак који се додаје у низ b је „ф“ као низ a не садржи га.

Објашњење # 2

низ има 4 слова „а“ док је низ има 5. Дакле, додатно слово је „а“.

Приступ (сортирање)

Можемо сортирати обе жице, а затим их обнављати слово по слово да бисмо пронашли прву позицију у којој се разликују. Други низ ће га увек имати екстра карактер. Дакле, увек ћемо наћи тачку где стринг a b разликује се. Међутим, може постојати случај када стринг b након сортирања одговара сваком знаку у низу a у, али на крају има један додатни знак. Морамо се позабавити овим једним посебним случајем.

Пронађите решење Леетцоде решење

Алгоритам

  1. Поредај обе жице, a b. Како то није могуће у јави, прво их претварамо у низови цхар
  2. За сваки знак присутан у краћем низу вршимо проверу слова по слово:
    • Ако је знак у низу није једнак одговарајућем знаку у низу b:
      • врати овај лик.
  3. Врати последњи знак низа као што је то додатни лик
  4. Одштампајте резултат

Примена решења за проналажење разлике у шифри

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Јава Програм

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

Анализа сложености решења за проналажење разлике у леетцоде-у

Сложеност времена

О (НлогН), где је Н = дужина дужег низа. Сортирамо низове / низове цхар којима је потребно О (НлогН) време.

Свемирска сложеност

НА) у јави и О (1) у Ц ++ док конвертујемо низове у цхар Арраис у јави.

Приступ (хеширање)

У оба низа можемо хеширати сваки знак са његовом фреквенцијом и пронаћи лик који се разликује у фреквенцији. Пошто имамо константан број јединствених ликова. Овај алгоритам је бржи од горе поменутог. Као ефикасну примену можемо створити хасх табле и повећајте фреквенцију за сваки знак у низу a и смањите фреквенцију за сваки знак у низу b. Ово ће нас оставити у случају да је фреквенција тачно једног знака не-нула а ово ће бити додатни знак у низу b.

Алгоритам

  1. Иницијализујте хеш табелу како бисте учитали фреквенцију свих знакова као фреквенција
  2. За сваки знак у низу a:
    • повећајте његову фреквенцију у хеш табели
  3. За сваки знак у низу b:
    • смањите његову фреквенцију у хеш табели
    • Ако је његова учесталост једнака -1:
      • врати овај лик
  4. Повратак '-' за одржавање синтаксе функције
  5. Одштампајте резултат

Примена решења за проналажење разлике у шифри

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Јава Програм

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

Анализа сложености решења за проналажење разлике у леетцоде-у

Сложеност времена

НА), Н = величина дужег низа, док једном прелазимо кроз оба низа да бисмо ажурирали њихове фреквенције знакова.

Свемирска сложеност

О (1). Иако користимо хештабле за похрану ликова са њиховим фреквенцијама, користимо константан простор без обзира на улаз. Дакле, сложеност простора је константна.