Пронајдете го решението за разлики за лет код


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Google
Хашинг Стринг

Во овој проблем, ни се дадени две жици. Втората низа се генерира со мешање на ликовите од првата низа по случаен избор и потоа додавање на дополнителен карактер во која било случајна позиција. Треба да го вратиме дополнителниот карактер што беше додаден на втората низа. Ликовите секогаш ќе бидат англиски букви со мали букви.

пример

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

Објаснување # 1

Дополнителниот карактер што се додава на низата b е 'f' како низа a не го содржи.

Објаснување # 2

Стринг има 4 'а' букви додека е низа има 5. Значи, дополнителното писмо е „а“.

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

Можеме да ги подредиме и жиците и потоа да ги повторуваме и двајцата буква по буква за да ја најдеме првата позиција каде што се разликуваат. Втората низа секогаш ќе има една дополнителни карактер Значи, секогаш ќе најдеме точка каде што е низа a b се разликува. Сепак, може да има случај кога низа b по сортирањето се совпаѓа со секој карактер во низата a во, но има еден дополнителен карактер на крајот. Треба да се справиме со овој еден посебен случај.

Пронајдете го решението за разлики за лет код

Алгоритам

  1. Сортирај ги и жиците, a b. Бидејќи не е можно во Java, ние прво ги претвораме во низи од јаглен
  2. За секој знак присутен во пократката низа, правиме проверка буква по буква:
    • Ако карактерот во низата не е еднаков на соодветниот знак во низата b:
      • врати го овој лик.
  3. Врати го последниот знак на низата бидејќи тоа е дополнителен карактер
  4. Печатете го резултатот

Имплементација на Пронајдете го решението за разлики за леткод

Програма C ++

#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;
}

Програма за Java

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

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

Временска комплексност

О (NlogN), каде што N = Должина на подолгата низа. Ние ги подредуваме низите / јагленовите низи за кои е потребно време O (NlogN).

Комплексноста на просторот

НА) во јава и О (1) во C ++ додека ги конвертираме низите во char низи во јава.

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

И во двата низа, можеме да го хашираме секој карактер со својата фреквенција и да го најдеме карактерот што се разликува во фреквенцијата. Бидејќи имаме постојан број на уникатни карактери. Овој алгоритам е побрз од оној дискутиран погоре. Како ефикасна имплементација, можеме да создадеме хаш-маса и зголемете ја фреквенцијата за секој карактер во низата a и намалете ја фреквенцијата за секој знак во низата b. Ова ќе не остави во случај кога фреквенцијата на точно еден карактер е не-нула и ова ќе биде дополнителен карактер во низата b.

Алгоритам

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

Имплементација на Пронајдете го решението за разлики за леткод

Програма C ++

#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;
}

Програма за Java

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

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

Временска комплексност

НА), N = големина на подолгата низа, како што поминуваме низ двата низа еднаш за да ги ажурираме нивните фреквенции на карактерот.

Комплексноста на просторот

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