BM22. [比较版本号]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM22. 比较版本号
题目的主要信息：
- 给出2个版本号version1和version2，比较它们的大小
- 版本号是由修订号组成，修订号与修订号之间由一个"."连接
- 修订号可能有前导0，按从左到右的顺序依次比较它们的修订号，比较修订号时，只需比较忽略任何前导零后的整数值
- 如果版本号没有指定某个下标处的修订号，则该修订号视为0
- 版本号中每一节可能超过int的表达范围
方法一：流输入截取
具体做法：
可以通过字符串流输入按点进行分割，将两个版本号字符串通过分割得到修订号的数组。然后同时遍历两个数组，将数组的字符串组成数字再判断数字的大小关系。
需要注意，有可能某一个版本号比另一个短，修订号更少，此时应该比较下标i与修订号数组，对于越界情况需要直接取0.
class Solution {
public:
int compare(string version1, string version2) {
vector<string> nums1;
vector<string> nums2;
istringstream sin1(version1);
istringstream sin2(version2);
string temp;
while(getline(sin1, temp, '.')) //流输入分割
nums1.push_back(temp);
while(getline(sin2, temp, '.'))
nums2.push_back(temp);
for(int i = 0; i < nums1.size() || i < nums2.size(); i++){
string s1 = i < nums1.size() ? nums1[i] : "0"; //较短的版本号取0
string s2 = i < nums2.size() ? nums2[i] : "0";
long long num1 = 0;
for(int i = 0; i < s1.length(); i++) //字符串转数字
num1 = num1 * 10 + (s1[i] - '0');
long long num2 = 0;
for(int i = 0; i < s2.length(); i++)
num2 = num2 * 10 + (s2[i] - '0');
if(num1 > num2) //比较数字大小
return 1;
if(num1 < num2)
return -1;
}
return 0;
}
};
复杂度分析：
- 时间复杂度：
，其中
和
分别为两个字符串的长度，流输入相当于遍历字符串，复杂度选取较高值
- 空间复杂度：
方法二：遍历直接截取
具体做法：
利用两个指针表示字符串的下标，分别遍历两个字符串，每次截取点之前的数字字符组成数字，因为int会溢出，这里采用long long记录数字，然后比较两个数字大小，根据大小关系返回1或者-1，如果全部比较完都无法比较出大小关系，则返回0.
class Solution {
public:
int compare(string version1, string version2) {
int n1 = version1.size();
int n2 = version2.size();
int i = 0, j = 0;
while(i < n1 || j < n2){//直到某个字符串结束
long long num1 = 0;
while(i < n1 && version1[i] != '.'){ //从下一个点前截取数字
num1 = num1 * 10 + (version1[i] - '0');
i++;
}
i++; //跳过点
long long num2 = 0;
while(j < n2 && version2[j] != '.'){ //从下一个点前截取数字
num2 = num2 * 10 + (version2[j] - '0');
j++;
}
j++; //跳过点
if(num1 > num2) //比较数字大小
return 1;
if(num1 < num2)
return -1;
}
return 0; //版本号相同
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
，无额外空间
得物app公司福利 402人发布
