轉換INT到串減少時間計算其長度

下面的代碼塊的複雜性：轉換INT到串減少時間計算其長度

Scanner in=new Scanner(System.in); 
int n=in.nextInt(); 
//converting the integer to string and calculating 
//its length reduces the complexity 
//to O(n) as compared to O(n^2) 
String str=Integer.toString(n); 
int length=str.length();length-=1;

我發現this code here。

我的問題是如何改變int爲字符串減少時間複雜性？

來源

2017-06-02 Anirudh Balakka

我投票關閉這一問題作爲題外話，因爲它要求通過互聯網上的一些隨機的人解釋不正確的陳述。 – Dukeling

代碼的作者聲稱它降低了複雜性相比，另一種解決方案發布：

#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    int num,d,rev=0; 

    cin>>num; 

// reverse a no. 
    while(num!=0) 
    { 
    d=num%10; 
    rev=rev*10+d; 
    num=num/10; 
    } 

    // using digits of reversed no. 
    while(rev!=0) 
    { 
    d=rev%10; 
    cout<<d*d; // printing square 
    rev=rev/10; 
    } 

return 0; 
}

這是假的，這兩種解決方案具有相同的複雜性，O(n)。

來源

2017-06-02 06:30:42 syntagma

即使使用簡單的while循環找到整數的長度爲O（n），而不是O（n^2）。

考慮下面的代碼片段：

while(n!=0) 
{ 
    n/=10; 
    ++count; 
}

來源

2017-06-02 06:37:05 sjboss

轉換INT到串減少時間計算其長度

回答

相關問題