10.17

3551先把原数组处理成数位和然后进行一次冒泡排序统计冒泡排序当中的交换次数存在问题就是冒泡排序的交换次数并不一定是最优的以及在转到数位和时会丢失信息最后要求数位和相等时还必须比较原数要求字典序最小官方题解并查集AI题解这个是怎么得到原数字到目标数组中的下标的sorted[i]是按规则对原数组排好序的不过并没有修改元素所以sorted[i]当中的元素值依然是nums中的那些元素值那就是说sorted[i]是nums中的某个元素其在Nums中的位置可能并不在i上但是排好序后就在i上了所以就是说对于Nums中sorted[i]的这个元素值其所在的位置就该是i即建立了sorted[i]-i的一个映射即原数字到目标数组中的下标的一个映射置换环对于任意的排序问题是否都存在置换环即排序前到下标到目标的映射关系最终是否一定会成环当得到置换环后如何知道最少需要几次交换对于长度为k的环要交换k-1次首先它是个环其次它的含义是环上每个位置指向它所要去的地方那么就是说在有n个元素的情况下其中有k个元素不在它所应该在的位置上对于未排序的元素如果有一个元素a未排序那么必然存在另一个元素b没有被排序因为a所在的位置是b的位置然后b所在的位置依然没排序它所占的可能是a也可能是c以此类推一定有一个未排序的元素占的是a的位置不过如何证明这样的结构最终所形成的一定是环依据环的性质先是不断任意交换缩减环的规模每次交换都会使环上元素减一即有一个元素到该到的位置上了等到环的规模到2时一次交换就能同时复原两个元素即直接从2变到0且特性也决定了环的大小至少是2即至少存在两个位置不对的元素而不存在一个位置不对的元素所以大小从k到2需要k-2次交换只剩两个时一次交换即可即k-21k-1次但是如何证明或保证只有最后一次交换时才可能出现一次交换能有两个元素归位的情况而其余情况时一次交换只能有一个元素归位为什么“任何排列都可以唯一分解成若干个不相交的环”以及这个分解如何得到DEBUG这里排序是直接在原数组上排序出错了因为nums已经排好序了那么在找环的时候首先找环所用到的数组一定是没排序时的数组Nums都已经排好序了那自然也就不存在环了不过用到的既然是原数组那为什么要求排序后的数组呢就是因为要知道排好序后原数组里的每个元素对应的最终位置是哪里设为tar那么就继续找原数组当中tar位置上的未排序数组所应该去的地方最终形成环在找环时写的比较绕是因为哈希表建立的是未排序元素值与其对应下标的关系而非未排序下标与其应该所在的下标之间的对应关系所以如果再构建一个数组来记录原下标i应该去的最终下标的话后面找环就不用写的那么绕即每个原下标i值为Ori[i]最终去的位置是pos[ori[i]]那么就建立映射i-pos[ori[i]]即p[i]pos[ori[i]]