Блог

Главная - Вопросы по программированию - Получение символов из вектора строк

Получение символов из вектора строк

#c #string #vector #mapping

#c #строка #вектор #отображение

Вопрос:

У меня есть строковый вектор, и я пытаюсь добраться до каждого символа каждого слова, используя два цикла, как показано ниже. Есть ли способ не использовать два цикла, чтобы я не выходил за рамки O (n) временной сложности.

уточнение: то, что я пытаюсь сделать, это преобразовать буквы в цифры, как в клавиатуре телефона, а затем выполнить поиск по этим номерам, если они доступны в строке PhoneNumber .

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

  // vector<string> words={"foo","bar","car","cat","lawyer"};
  // string phoneNumber="3226773664"

  void lookup(vector<string> amp;words,string phoneNumber){
  string strtonumber="";
  int ascii;

  for(auto word:words ){
    strtonumber="";
    for(auto chr:word ){
      ascii=int(chr);

      if(ascii >= 97 amp;amp; ascii<=99)
      strtonumber ="2";
      if(ascii >= 100 amp;amp; ascii<=102)
      strtonumber ="3";
      if(ascii >= 103 amp;amp; ascii<=105)
      strtonumber ="4";
      if(ascii >= 106 amp;amp; ascii<=108)
      strtonumber ="5";
      if(ascii >= 109 amp;amp; ascii<=111)
      strtonumber ="6";
      if(ascii >= 112 amp;amp; ascii<=115)
      strtonumber ="7";
      if(ascii >= 116 amp;amp; ascii<=118)
      strtonumber ="8";
      if(ascii >= 119 amp;amp; ascii<=122)
      strtonumber ="9";
  
    }
    
     if (phoneNumber.find(strtonumber) != string::npos)
        cout<<"Numerical version of these words available in your Phone Number string"<<endl;
  }

Комментарии:

1. Что вы подразумеваете под не выходить за пределы O (n) ? Использование нескольких вложенных циклов не всегда означает, что временная сложность нелинейна, в вашем случае временная сложность равна O(sum of words' length)

2. Я согласен, что в худшем случае сложность равна O (количество слов x самое длинное слово в векторе). Но я пытаюсь как-то избавиться от вложенных циклов, насколько это возможно

3. не зацикливайтесь на нотации big O. Недоразумения, основанные на big-O, довольно распространены. Ваш код имеет сложность O(n) для доступа n к символам. Вы не получите намного быстрее

4. Почему? во вложенных циклах нет ничего плохого. Конечно, вы могли бы использовать какой-то подход с одной ответственностью и поместить внутренний цикл в отдельную функцию. Но всегда будут циклы.

5. что именно вы хотите сделать в некоторых вещах.

Ответ №1:

Есть ли способ не использовать два цикла, чтобы я не выходил за рамки O (n) временной сложности.

Вложенные циклы не всегда O(N^2) . Или, точнее: big-O имеет смысл только тогда, когда вы говорите, что N есть. Этот цикл имеет сложность O(N^2) :

 for (unsigned i=0; i < N;   i) {
     for (unsigned j=0; j < N;   j) {
          foo(i,j);                // <- this is called N*N times
     }
}

Однако ваши циклы довольно похожи на

 for (unsigned i=0; i < number_of_strings;   i) {
     for (unsigned j=0; j < number_of_characters(i);   j) {
          foo( words[i][j] );
     }
}

И O( number_of_strings * number_of_characters ) это не что иное O(N) , как когда N — это количество символов, которые вы хотите обработать.

Другой способ подумать об этом — рассмотреть , что изменится в отношении сложности , если вы будете выполнять те же операции со строкой "foobarcarcatlawyer" . Ничего. Если вы повторяете эту строку, количество раз, когда вы преобразуете один символ, остается точно таким же.

Вы не можете обрабатывать N символы менее чем O(N) за .