1、给定升序自然数数组,数字有重复,二分算法求给定任意数字位置,参数决定是给定数字的开始位置还是结束位置。 这里关键是开始结束位置的高效判定,代码如下。 2、给定一个乱序的自然数数组,求里面的数字能够组成最长连续数组的长度,例如给定[100,2,1,3],有[1,2,3],所以返回值为3,要求复杂度O(n)。 直接做的话,复杂度是nlog(n)的,用一个hash表的方法,复杂度为O(数组中最大数-数组中最小数),目测还不如直接做,n复杂度的如下。
这里关键是开始结束位置的高效判定,代码如下。
2、给定一个乱序的自然数数组,求里面的数字能够组成最长连续数组的长度,例如给定[100,2,1,3],有[1,2,3],所以返回值为3,要求复杂度O(n)。 直接做的话,复杂度是nlog(n)的,用一个hash表的方法,复杂度为O(数组中最大数-数组中最小数),目测还不如直接做,n复杂度的如下。
浙公网安备 33010602006230号
浙ICP备14015892号