Algorithm 题解目录 | Thinkwee's Blog

Algorithm 题解目录 | Thinkwee's Blog

75:给出一个只包含0，1，2的数列，排序形成[0,0,…,0,1,…,1,2,…,2]的形式，在原数列上修改。借鉴Lomuto partition algorithm，维护三个区间[0,i],[i,j],[j,k]为0，1，2的范围，按优先级，若当前数为2或1或0，先将nums[k]=2，k++，若当前数为1或0，则nums[j]=1,j++，若当前数为0,则nums[i]=0,i++，越往后能覆盖前面的，优先级越高。

164：给出一个无序数列，请在O(n)时间复杂度内找到数列有序化后相隔元素差最大值。桶排序，设数列中最大值最小值分别为max,min,易得这个相邻元素差最大值肯定大于(max-min)/(n-1)并设这个值为gap，n是数列长度。将数列的取值区间[min,max]以(max-min)/(n-1)为间隔分成nums个桶，nums是int((max - min) / gap + 1)，把数列各个元素分到桶中，每个桶只存对应区间内的最大元素和最小元素，把那么最大间隔肯定在相邻两个桶的边界处（前一个桶的最大值和后一个桶的最小值），因为桶内的最大间隔小于gap。最后遍历一遍桶就可以了。

Read full article from Algorithm 题解目录 | Thinkwee's Blog