专栏首页小数志Python变量并列赋值的疑问

Python变量并列赋值的疑问

近日在刷leetcode时,遇到这样一道题:

问题:索引从0开始长度为N的数组A,包含0到N - 1的所有整数。找到并返回最大的集合S,S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。

假设选择索引为i的元素A[i]为S的第一个元素,S的下一个元素应该是A[A[i]],之后是A[A[A[i]]]... 以此类推,不断添加直到S出现重复的元素。

示例 1:

输入: A = [5,4,0,3,1,6,2]

输出: 4

解释:

A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6]= 2.

其中一种最长的 S[K]: S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

来源:力扣(LeetCode)题号:565

链接:https://leetcode-cn.com/problems/array-nesting


题目本身不难,从起点开始顺序遍历,同时用一个观测数组标记当前值已进行探测,避免重复遍历。

个人的源代码

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        seen = [False]*len(nums)#观测列表
        maxLength = 0
        for i in range(len(nums)):
            if seen[i]:
                continue
            nxt, curLength = i, 0
            while not seen[nxt]:
                curLength += 1
                seen[nxt], nxt = True, nums[nxt]
            maxLength = max(maxLength, curLength)
        return maxLength

程序运行正确,提交结果也不错

该方案的时空复杂度均为O(n)。看了官方题解后,发现有可以实现空间复杂度O(1)的方案,即利用原数组nums进行标记当前值已完成探测。这样虽然丢失了原数组元素,但确实带来了空间复杂度的提升(leetcode上很多题目都有类似做法)。

于是,自己也尝试了一下这种写法,却遇到了一个不大不小的坑。

Python最引以为傲的一个特性是可以原地交换两个变量的值,既简洁又高效。这其中的原因在于python的变量存储的是地址而非实际数据,所以当交换两个变量时实际上是交换了地址引用。

a, b = b, a

基于此,原代码中无需开辟标记数组seen,而直接用原数组nums替代。即

#开辟观测数组方案
seen[nxt], nxt = True, nums[nxt]
#利用原数组标记方案
nums[nxt], nxt = -1, nums[nxt]

其中,对于遍历过的nums[nxt]赋值为-1(原数组中的元素取值范围为0-n-1,因为要作为索引下标使用),表示已经探测。

改动不大,但运行结果差别却很大。

为了表述方便,将前面关键代码简化表达,并给出引起歧义的两种方案表述:

b, a[b] = a[b], -1#索引在前,列表在后
a[b], b = -1, a[b]#列表在前,索引在后

如果a, b = b, a是绝对平行赋值的话,那么两种方案运行结果应该是一致的。但现实情况让人大跌眼镜:

运行结果1

运行结果2

在尝试解释这个问题前,我们先试验一个python变量赋值的小例子:

可以发现,python中对变量的赋值实际上是取决于变量对应数值的,当变量的赋值一致时,无论来源如何(初次赋值、再次赋值或者是由其他计算得到),只要赋值相同就都指向同一地址。

所以在上述例子中,a、b和c三者的地址一致,而d虽然字面值也一致,但数据类型不一致,所以重新赋值。

当然,a、b和c变量地址一致并不意味着改变其中一个变量,其他变量同步改变,而实际上是指向新的字面值对应地址。所以b从1赋值为2后,地址有所改变,而a、c地址不变,值也不变。

所以,在python变量管理中,值的地址决定了变量的地址,而非变量存储了值的大小。

所以,现在我们回过头来分析代码中那个坑,似乎可以做出如下推断:

  • 无论是可变类型(列表、字典等)还是不可变类型(基本数据类型,整型、字符串等),都是基于值的地址赋值和引用;
  • 两个变量并列赋值时,先后顺序可能会有影响,意味着a, b = b, a 不同于 b, a = a, b;
  • 并列赋值时,先保留等号右侧的取值,再依次赋值给等号左侧的变量。所以,
    • 在"a[b], b = -1, a[b]"中,先保留等号右侧的取值-1和0,然后分别对左侧的变量赋值,即a[b]=-1(此时a[b]是a[1]),b=0;
    • 而"b, a[b] = a[b], -1"中,先保留等号右侧的取值0和-1,然后分别对左侧的变量进行赋值,即b=0,a[b]=-1(此时a[b]已变为a[0])。

#以上推断纯属个人试验,尚缺乏权威论证。

本文分享自微信公众号 - 小数志(Datazhi),作者:luanhz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python中几个有趣的函数

    众所周知,python功能强大、语法灵活,这些得益于其丰富而强大的库。除了众多第三方库和方法函数,python自带的很多函数也非常有趣,用起来称得上优雅。

    luanhz
  • 瓜子二手车市场分析(Scrapy+Tableau)

    本文对瓜子网杭州二手车进行了爬取和简单分析,一方面是为了进一步熟练使用Python的Scrapy爬虫框架,另一方面是为了熟悉Tableau强大的数据可视化功能。

    luanhz
  • 应用scrapy爬虫框架

    scrapy=scrap+python,是python自动化爬虫框架,相当于一个模板。当启动了一个scrapy工程后,会自动生成若干相互关联的文件,用户仅需根据...

    luanhz
  • GDB 常用的调试命令概览

    一旧
  • Java反射(一)

    Java学习123
  • 计算机_网络_01_配置IE代理

    shirayner
  • lucene实例与源码解析

    全文检索的引擎工具包,实现了全文检索的类库。 全文检索,将查询的目标对象提取出来构造一套索引,查询索引得到数据结果。

    用户7625070
  • 如何在CDH集群中安装Hive2.3.3

    Fayson
  • Keepalived使用梳理

    keepalived介绍 keepalived观察其名可知,保持存活,在网络里面就是保持在线了,也就是所谓的高可用或热备,它集群管理中保证集群高可用的一个服务软...

    洗尽了浮华
  • 如何在Redhat7.4安装HDP3.0.1

    7月13日,Hortonworks在其官网宣布发布HDP3.0,相关介绍可以参考Fayson昨天的文章《Hortonworks正式发布HDP3.0》,最近又更新...

    Fayson

扫码关注云+社区

领取腾讯云代金券