A random string is given. For example, 4jkk8653kl87-43 @ Wf23457754345. Is it possible for O (n) to extract from the system in order, from left to right, all int type numbers into an array? For our example: 4,8653,87, -43.

  • one
    What is the term "without nested cycles"? If you mean "in one pass through the line" - then you can. I don’t know how to implement this without nested loops at all. - andy.37
  • @ andy.37 Quadratic complexity and linear - is there a difference? - Georgiy_Barsukov
  • @ georgiy-barsukov. There is. Therefore, I clarify. Nested loops in the algorithm will be, but the complexity will be linear - andy.37
  • @ andy.37 understood, changed the question - Georgiy_Barsukov
  • 2
    @Umed, since when do regularizers have linear asymptotics? In addition, they will get the result in the form of lines. - Qwertiy ♦

7 answers 7

 char c[] = "sadfaghf123454hfdgsh4352hdgf43256"; while (c[i] != '\0') { if (c[i] >= '0' && c[i] <= '9') i = get_number(c+i, next_number); // i - след. индекс не цифры, в нумбер пишем число. else i = skip_non_digit_chars(c+i); // i - след. индекс цифры bkb '\0' }

In functions get_number and skip_non_digit_chars will be cycles of type while (is_digit(c[i])) { ...}

This, of course, is not a solution, so a sketch of the algorithm, but here they do not like to do the tasks for you entirely

  • one
    while (c[i] != '\0') - Georgiy_Barsukov
  • @Georgiy_Barsukov, ATP, ochepyatka essno. - andy.37

http://ideone.com/fGuRWG

 #include <iostream> #include <vector> using namespace std; int main (void) { const char *s="4jkk8653kl87-43@Wf23457754345", *p; vector <long long> res; long long cur; bool neg; for(p=s; *p; ++p) if(*p=='-' || *p>='0' && *p<='9') { cur = (neg = *p=='-') ? 0 : *p-'0'; while(*++p>='0' && *p<='9') cur = cur*10 + *p - '0'; --p; res.push_back(neg ? -cur : cur); } for(unsigned q=0; q<res.size(); ++q) cout << res[q] << ' '; return 0; }
  • one
    readable) - Georgiy_Barsukov
  • Ha! ... for(...) if(...) while(...) { ... } . This is not a nested loop ?! ))) But beautiful. - andy.37
  • vector can be removed and output values ​​immediately. - αλεχολυτ
  • By the way, your output is: 4 8653 87 -43 23457754345 - Georgiy_Barsukov
  • @ andy.37 and how did you want to check the character on the number without a cycle? Expand it in a chain of if? It will be really funny. I would suggest using isdigit , there may be a table function (i.e., without cycles). - αλεχολυτ

http://ideone.com/Qu5xmY is a variant without nested loops.

 #include <iostream> #include <vector> using namespace std; int main (void) { const char *s="4jkk8653kl87-43@Wf23457754345", *p; vector <long long> res; long long cur; bool in=false, neg; for(p=s; *p; ++p) if(in) if(*p>='0' && *p<='9') cur = cur*10 + *p - '0'; else res.push_back(neg ? -cur : cur), in=false, p-=*p=='-'; else if((neg=*p=='-')) in=true, cur=0; else if(*p>='0' && *p<='9') in=true, cur=*p-'0'; if(in) res.push_back(cur); for(unsigned q=0; q<res.size(); ++q) cout << res[q] << ' '; return 0; }

Just in case: https://ru.stackoverflow.com/questions/473901/%d0%9f%d0%be%d1%87%d0%b5%d0%bc%d1%83-%d0%b1%d0% b5% d1% 81% d0% ba% d0% be% d0% bd% d0% b5% d1% 87% d0% bd% d1% 8b% d0% b9-% d1% 86% d0% b8% d0% ba % d0% bb

    Here is a demo program that shows how this can be done.

     #include <iostream> #include <string> #include <vector> #include <cstdlib> int main() { std::string s( "4jkk8653kl87-43@Wf23457754345" ); std::vector<int> v; for ( std::string::size_type pos = 0; ( pos = s.find_first_of( "0123456789", pos ) ) != std::string::npos; ) { char *p; int value = ( int )std::strtol( s.c_str() + pos, &p, 10 ); v.push_back( value ); pos = p - s.c_str(); } for ( int value : v ) std::cout << value << ' '; std::cout << std::endl; }

    The output of the program to the console:

     4 8653 87 43 2147483647

    Since you may have very long values, instead of the int type, it is better to use the long long int . For example,

     #include <iostream> #include <string> #include <vector> #include <cstdlib> int main() { std::string s( "4jkk8653kl87-43@Wf23457754345" ); std::vector<long long int> v; for ( std::string::size_type pos = 0; ( pos = s.find_first_of( "0123456789", pos ) ) != std::string::npos; ) { char *p; long long int value = std::strtoll( s.c_str() + pos, &p, 10 ); v.push_back( value ); pos = p - s.c_str(); } for ( long long int value : v ) std::cout << value << ' '; std::cout << std::endl; }

    Then for long sequences of numbers the result will be more accurate.

     4 8653 87 43 23457754345

    Compare the previous output of the last number and the output of the last number.

    If the dash is not a separator, but a minus sign, then you just need to add it to the search characters. The program will look like this.

     #include <iostream> #include <string> #include <vector> #include <cstdlib> int main() { std::string s( "4jkk8653kl87-43@Wf23457754345" ); std::vector<long long int> v; for ( std::string::size_type pos = 0; ( pos = s.find_first_of( "-0123456789", pos ) ) != std::string::npos; ) { char *p; long long int value = std::strtoll( s.c_str() + pos, &p, 10 ); if ( !( value == 0 && p[-1] != 0 ) ) v.push_back( value ); pos = p - s.c_str(); } for ( long long int value : v ) std::cout << value << ' '; std::cout << std::endl; }

    Then the console output g will look like

     4 8653 87 -43 23457754345
    • Well all of you push long int in int . Generally speaking it is incorrect. This is perhaps the most modern solution, although, in my opinion, the problem asks for solutions on pure C. - andy.37
    • @ andy.37 Regarding incorrectness, you can write a letter to the Standards Committee C and report that the atoi function is incorrect. So this question is not for me. Or you can just read a book on C. - Vlad from Moscow
    • And nothing that you have found 43 instead of -43 ? - Qwertiy ♦
    • @ vlad-from-moscow, and where does the standard come from? In the original example (where vector<int> ) you assign the result int to the variable int to the strtoll function. It will work, but the number may turn out different. To the second sample code, there are no complaints. (and the first is not a claim, so, rather, a remark). By the way, what if the number in the string and in the long long does not fit. Funny, simple, like, question, and what a discussion)) - andy.37
    • @ andy.37 Standard despite the fact that you do not seem to know how the atoi function is defined. Therefore, I advise you to read a book on C / - Vlad from Moscow

    Option without nested loops with computational complexity O (n) .

     #include <string> #include <iostream> using namespace std; const string s("4jkk8653kl87-43@Wf23457754345"); int start = -1; int count = 0; inline bool isDigit(const char c) { return '0' <= c && c <= '9'; } void newNumber() { cout << s.substr(start, count) << endl; start = -1; count = 0; } int main() { for (int i = 0; i < s.length(); ++i) { if (s[i] == '-') { if (start >= 0) { newNumber(); } if (start < 0 && i+1 < s.length() && isDigit(s[i+1])) { start = i; ++i; count = 2; continue; } } else if (isDigit(s[i])) { if (start < 0) start = i; ++count; continue; } if (start >= 0 && count > 0) newNumber(); } if (start >= 0 && count > 0) newNumber(); return 0; }

    PS String does not convert to number. This is just a parsing implementation. If you need to convert, change the function newNumber .

      The algorithm may be as follows:
      1. Select substrings from numbers (possibly with a sign) into an array.
      2. Read each substring as a float number.
      3. If the resulting number does not go beyond the int format, write it into the result array as int.

      In PHP, the program looks like this:

       $maxint = getrandmax(); $str = "4jkk8653kl87-43@Wf23457754345"; print "str = $str"; $cnt = preg_match_all("/[+-]?[0-9]+/", $str, $matches); $arr = []; foreach($matches[0] as $strnum){ sscanf($strnum, "%f", $number); if(($number >= -$maxint-1) && ($number <= $maxint)){ $arr[] = (int)$number; } } var_dump($arr);

      The result is:

       str = 4jkk8653kl87-43 @ Wf23457754345
 array (size = 4)
   0 => int 4
   1 => int 8653
   2 => int 87
   3 => int -43

         #include <bits/stdc++.h> #include <string.h> #define pb push_back #define mp make_pair #define F first #define S second #define sz(x) (int)x.size() #define str(x) (int)strlen(x) #define all(x) x.begin(), x.end() #define itr ::iterator #define rt return #define sf scanf #define pf printf #define bit __builtin_popcountll #define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++) #define SABR inline ll IN(){ll x=0,ch=getchar(),f=1;while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();if (ch=='-'){f=-1;ch=getchar();}while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}inline void OUT(ll x){if (x<0) putchar('-'),x=-x;if (x>=10) OUT(x/10),putchar(x%10+'0');else putchar(x+'0');} #define PI 3.14159265358979323846264338327950288419716939937510 using namespace std; typedef long long ll; typedef unsigned uns; typedef pair <int, int> pi; typedef vector <int> vi; const int MX = (int) 1e6 + 17; const int MOD = (int) 1e9 + 7; const ll LINF = (ll) 1e18 + 7; const int INF = (int) 999999999; SABR string s; vector <int> numbers; int main() { cin >> s; for (int i = 0; i < sz(s); i++) { if (s[i] >= '0' && s[i] <= '9') { int x = 0; while (s[i] >= '0' && s[i] <= '9') { x += s[i] - '0'; x *= 10; i++; } numbers.pb(x / 10); } } for (int i = 0; i < sz(numbers); i++) cout << numbers[i] << ' '; return 0; }

        As for me, this is the most understandable code. Nothing superfluous and asymptotics O (n);