目录

LeetCode—面试题 16.06. 最小差

01题目描述:

面试题 16.06. 最小差
给定两个整数数组a和b,计算具有最小差绝对值的一对数值(每个数组中取一个值),并返回该对数值的差


示例:

输入:{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出: 3,即数值对(11, 8)
提示:

1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
正确结果在区间  [-2147483648, 2147483647]

02题目分析:

两个列表的最小差,这一个题目我刚刚看到的时候,我想用一个列表的最大和另外一个列表的最小相减就是最小差啊!其实不然。。。都是我想当然了!
最小差,这一个差就是代表了!!!差具有非负性!!,最小的差就是两个数相等相减为0!所以我们要找的是两个列表中最接近的两个数值!然后最差之后去绝对值!abs(差) 这样取出来的就是最小值!
1、0 一定是最小的差,我们进行循环遍历获取最小的差,如果看到了差为0,就直接返回了!不用继续的循环遍历了,节省运行时间,减少无效循环!
2、获取最小的方式有很多!可以吧所有的差值全部添加到一个列表,最后用min(list),或者循环的时候把获取的差值与最小的差值作比较,然后minnum = min(minnum,差),这样保证了minnum一直都是最小值。最后返回计科!


03-1方法A

代码A:

class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        ia,ib=0,0
        list1=[]
        while ia<len(a):
            while ib<len(b):
                num =a[ia]-b[ib]
                list1.append(abs(num))
                if num>0:
                    ib+=1
                    # break
                elif num==0:
                    return 0
                else:
                    ia +=1
                    break
            # return min(list1)

运行结果A:

1.时间运行情况A:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP

2.内存使用情况A:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP
~~========================================================================~~

03-2方法B

方法B,就是对方法A的,两个 while 循环嵌套的优化,变成一个while循环,降低了复杂度!效率提高了,运行时间自然就缩短了。只有两个循环条件都满足的情况下,才进行循环。

代码B:

class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        ia,ib=0,0
        list1=[]
        while ia<len(a) and ib<len(b):
            num =a[ia]-b[ib]
            list1.append(abs(num))
            if num>0:
                ib+=1
            elif num==0:
                return 0
            else:
                ia +=1
                # 改变成为一个while循环就不需要break了!
                # break
        return min(list1)

运行结果B:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP

1.时间运行情况B:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP

2.内存使用情况B:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP
~~========================================================================~~

03-3方法C

方法C对于方法B的区别就是。在获取最小值的时候,B方法是全部添加到一个新的列表,最后的时候再去 min(list) 返回最小值,如果列表特别长的话就会影响运行。方法C就是用一个变量存储最小值,在前面定义变量为 nummin 一个无穷大的数值
(这里可定会有人疑惑,我定义一个无穷大的数值,为啥命名为nummin最小呢?其实我们这一个变量,主要是为了后面获取到最小值,因为我们后面需要这一个变量的数值与差值做比较获取最小的数值,然后重新把最小的数值赋值给nummin换一个角度理解,就是我们还没有获取到两个列表的任何一个差值,那么这两个列表的差值就是无限大。)
然后在后面与获取的差作比较,**然后赋值给这一个变量 nummin,**如此循环,保证nummin获取到的永远都是差值最小的那一个,最后返回!

代码C:


class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        ia,ib=0,0
        # list1=[]
        nummin = float('inf') # 获取一个无穷大的数值

        while ia<len(a) and ib<len(b):
            num =a[ia]-b[ib]
            nummin = min(abs(num),nummin)
            if num>0:
                ib+=1
            elif num==0:
                return 0
            else:
                ia +=1
        return nummin

运行结果C:

1.时间运行情况C:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP

2.内存使用情况C:

LeetCode刷题(0003)---面试题 16.06. 最小差,python3-LMLPHP

04结语:

个人记录,新手入门,多多学习,欢迎大家交流探讨!
个人网站: http://106.54.78.238/
song_of _sea的个人网站 http://106.54.78.238/

09-03 00:43