165. Compare Version Numbers
题目描述
Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
比价两个版本号的大小
解题思路
- 将string以"."隔断拆分成list,
- 短的list的索引范围内逐个比较两个list中元素的大小
- 还未比出大小的情况下, 说明两个list在一定范围内都相等, 但是(1) 可能存在长list长出的部分全为0(说明两个list大小相等). (2) 可能存在若干个0但是末尾元素大于0(说明此时长list一定大于短list).
- 时间 空间复杂度均为O(n)
代码
Python
class Solution:
def compareVersion(self, version1, version2):
version1 = [int(_) for _ in version1.split(".")]
version2 = [int(_) for _ in version2.split(".")]
# print(version1, version2)
len1 = len(version1)
len2 = len(version2)
for i in range(min(len1, len2)):
if version1[i] > version2[i]:
return 1
elif version1[i] < version2[i]:
return -1
diff = len1 - len2
if diff > 0 and version1[-1] != 0:
return 1
elif diff < 0 and version2[-1] != 0:
return -1
else:
return 0