澳门新莆京手机网站-新蒲京娱乐场 > 联系我们 > 常用排序算法之JavaScript完成

常用排序算法之JavaScript完成

countBits 的年华复杂度

考虑 countBits, 上边的算法:

  • “版本1” 的时辰复杂度是 O(N*M卡塔尔,M 决计于 Number.prototype.toString 和 String.prototype.replace 的复杂度。
  • “版本2” 的光阴复杂度是 O(N*logN)
  • “版本3” 的年月复杂度是 O(N*MState of Qatar,M 是 N 的二进制数中的“1”的个数,介于 1 ~ logN 之间。

地点几个版本的 countBits 的时刻复杂度都超过 O(N卡塔尔(قطر‎。那么有没一时间复杂度 O(N卡塔尔 的算法呢?

实际,“版本3”已经为我们提醒了答案,答案就在下边包车型地铁特别定律里,我把那多少个等式再写三遍:

countBit(n & (n - 1)) === countBit(n) - 1

1
countBit(n & (n - 1)) === countBit(n) - 1

也便是说,假如大家了然了 countBit(n & (n - 1)),那么大家也就理解了 countBit(n)

而笔者辈知晓 countBit(0) 的值是 0,于是,大家能够很简短的递推:

版本4

function countBits(nums){ var ret = [0]; for(var i = 1; i <= nums; i++){ ret.push(ret[i & i - 1] + 1); } return ret; }

1
2
3
4
5
6
7
function countBits(nums){
   var ret = [0];
   for(var i = 1; i <= nums; i++){
       ret.push(ret[i & i - 1] + 1);
   }
   return ret;
}

原本就像是此简单,你想到了吧 ╮(╯▽╰卡塔尔(قطر‎╭

上述正是有着的内容,简单的标题思忖起来很有趣吗?程序猿就应该追求完备的算法,不是吧?

那是 leetcode 算法面试题体系的首初期,下意气风发期我们议论除此以外风华正茂道题,这道题也很有趣:判别一个非负整数是还是不是是 4 的整数十次方,别告诉笔者你用循环,动脑更抢眼的点子吗~

打赏扶植自身写出更加的多好随笔,谢谢!

打赏我

解题思路

假设忽视“附加条件”,那题还挺轻松的对啊?大约是随手拈来:

版本1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
        num /= 4;
    }
    return num === 1;
}

本子1 相近相当的轻松、很强大的榜样,它的时刻复杂度是 log4N。有同学说,还能做一些微微的改换:

版本1.1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num >>>= 2; } return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
      num >>>= 2;
    }
    return num === 1;
}

上边的代码用位移替代除法,在别的语言中更加快,鉴于 JS 经常意况下特别坑的位运算操作,不肯定速度能变快。

好了,最着重的是,不管是 版本1 依然 版本1.1 就好像都不满足我们前面提到的“附加条件”,即不使用循环和递归,只怕说,大家须要探求O(1卡塔尔 的解法。

遵纪守法规矩,大家先研究10分钟,然后往下看 ——


常用排序算法之JavaScript实现

笔试面试平日提到种种算法,本文简单介绍常用的有的算法,并用JavaScript完毕。

 

1、插入排序

 1)算法简单介绍

 

  插入排序(Insertion-Sort)的算法描述是后生可畏种简易直观的排序算法。它的干活规律是透过创设有序体系,对于未排序数据,在已排序体系中从后迈入扫描,找到呼应地点并插入。插入排序在达成上,日常使用in-place排序(即只需用到O(1卡塔尔国的额外层空间间的排序),因此在从后迈入扫描进度中,供给每每把已排序元素日渐向后挪位,为新型因素提供插入空间。

 

2)算法描述和促成 

 

  平时的话,插入排序都利用in-place在数组上落到实处。具体算法描述如下:

 

从第一个因素开首,该因素得以以为已经被排序;

抽取下三个因素,在曾经排序的要素体系中从后迈入扫描;

借使该因素(已排序)大于新因素,将该因素移到下一人置;

再也步骤3,直到找到已排序的因素小于恐怕等于新因素的地点;

将新成分插入到该职分后;

再也步骤2~5。

  JavaScript代码实现:

 

复制代码

 1 function insertionSort(array) {

 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {

 3         for (var i = 1; i < array.length; i++) {

 4             var key = array[i];

 5             var j = i - 1;

 6             while (j >= 0 && array[j] > key) {

 7                 array[j + 1] = array[j];

 8                 j--;

 9             }

10             array[j + 1] = key;

11         }

12         return array;

13     } else {

14         return 'array is not an Array!';

15     }

16 }

复制代码

3)算法解析

 

最棒状态:输入数组按升序排列。T(n卡塔尔国 = O(n卡塔尔(قطر‎

最坏情状:输入数组按降序排列。T(n卡塔尔(قطر‎ = O(n2卡塔尔国

平均景况:T(n卡塔尔 = O(n2卡塔尔(قطر‎

二、二分插入排序

1)算法简单介绍

 

  二分插入(Binary-insert-sort卡塔尔排序是风度翩翩种在直接插入排序算法上海展览中心开小修正的排序算法。其与直接插入排序算法最大的界别在于搜索插入地方时使用的是二分查找的措施,在进程上有一定进步。

 

2)算法描述和实现  

 

  平常的话,插入排序都施用in-place在数组上得以达成。具体算法描述如下:

 

从第多个成分初阶,该因素得以以为曾经被排序;

收取下四个因素,在曾经排序的要素连串中二分查找到首个比它大的数的岗位;

将新成分插入到该地方后;

再一次上述两步。

  JavaScript代码实现:

 

复制代码

 1 function binaryInsertionSort(array) {

 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {

 3         for (var i = 1; i < array.length; i++) {

 4             var key = array[i], left = 0, right = i - 1;

 5             while (left <= right) {

 6                 var middle = parseInt((left + right) / 2);

 7                 if (key < array[middle]) {

 8                     right = middle - 1;

 9                 } else {

10                     left = middle + 1;

11                 }

12             }

13             for (var j = i - 1; j >= left; j--) {

14                 array[j + 1] = array[j];

15             }

16             array[left] = key;

17         }

18         return array;

19     } else {

20         return 'array is not an Array!';

21     }

22 }

复制代码

3)算法剖判

 

最好状态:T(n卡塔尔(قطر‎ = O(nlogn卡塔尔(قطر‎

最差景况:T(n卡塔尔(قطر‎ = O(n2卡塔尔国

平均景况:T(n卡塔尔(قطر‎ = O(n2卡塔尔

三、选用排序

1)算法简要介绍

 

  选取排序(Selection-sortState of Qatar是意气风发种简易直观的排序算法。它的做事规律:首先在未排序系列中找到最小(大)元素,贮存到排序系列的序曲地点,然后,再从剩余未排序成分中继续搜寻最小(大)成分,然后嵌入已排序体系的末尾。由此及彼,直到全部因素均排序实现。

 

2)算法描述和兑现

 

  n个记录的直白选取排序可通过n-1趟直接选用排序获得稳步结果。具体算法描述如下:

 

起来状态:冬日区为Escort[1..n],有序区为空;

第i趟排序(i=1,2,3...n-1卡塔尔国开头时,当前有序区和冬天区独家为凯雷德[1..i-1]和PRADO(i..n)。该趟排序从当前冬天区中选出第一字超小的笔录 Lacrosse[k],将它与冬辰区的首个记录PAJERO调换,使Tucson[1..i]和R[i+1..n卡塔尔国分别成为记录个数扩展1个的新有序区和笔录个数缩短1个的新冬辰区;

n-1趟甘休,数组有序化了。

  JavaScript代码实现:

 

复制代码

 1 function selectionSort(array) {

 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {

 3         var len = array.length, temp;

 4         for (var i = 0; i < len - 1; i++) {

 5             var min = array[i];

 6             for (var j = i + 1; j < len; j++) {

 7                 if (array[j] < min) {

 8                     temp = min;

 9                     min = array[j];

10                     array[j] = temp;

11                 }

12             }

13             array[i] = min;

14         }

15         return array;

16     } else {

17         return 'array is not an Array!';

18     }

19 }

复制代码

3)算法深入分析

 

最好状态:T(n卡塔尔国 = O(n2卡塔尔

最差情形:T(n卡塔尔国 = O(n2卡塔尔国

平均情形:T(n卡塔尔国 = O(n2卡塔尔(قطر‎

四、冒泡排序

1)算法简要介绍

 

  冒泡排序是大器晚成种简单的排序算法。它再也地拜望过要排序的数列,贰遍相比较八个成分,如若它们的次第错误就把它们沟通过来。拜望数列的劳作是再次地张开直到未有再供给沟通,也正是说该数列已经排序实现。那个算法的名字由来是因为越小的要素会路过调换稳步“浮”到数列的上方。

 

2)算法描述和贯彻

 

  具体算法描述如下:

 

相比相邻的要素。如若第三个比第二个大,就交流它们三个;

对每生机勃勃对左近成分作雷同的劳作,从上马首先对到结尾的最后有的,那样在最终的成分应该会是最大的数;

本着全部的因素重复以上的步子,除了最后叁个;

再一次步骤1~3,直到排序完毕。

  JavaScript代码完结:

 

复制代码

 1 function bubbleSort(array) {

 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {

 3         var len = array.length, temp;

 4         for (var i = 0; i < len - 1; i++) {

 5             for (var j = len - 1; j >= i; j--) {

 6                 if (array[j] < array[j - 1]) {

 7                     temp = array[j];

 8                     array[j] = array[j - 1];

 9                     array[j - 1] = temp;

10                 }

11             }

12         }

13         return array;

14     } else {

15         return 'array is not an Array!';

16     }

17 }

复制代码

3)算法深入分析

 

最棒状态:T(nState of Qatar = O(n卡塔尔

最差景况:T(n卡塔尔(قطر‎ = O(n2State of Qatar

平均景况:T(n卡塔尔 = O(n2卡塔尔国

五、快速排序

1)算法简要介绍

 

  快速排序的大旨境想:通过风流倜傥趟排序将待排记录分隔成独立的两有的,此中有的记下的第一字均比另后生可畏局地的第一字小,则可个别对这两片段记录继续开展排序,以高达整个系列有序。

 

2)算法描述和促成

 

  火速排序使用分治法来把三个串(list)分为三个子串(sub-lists)。具体算法描述如下:

 

从数列中挑出三个要素,称为 "基准"(pivot);

重复排序数列,全体因素比基准值小的摆放在基准前边,全体因素比基准值大的摆在基准的末端(相似的数能够到任后生可畏边)。在这里个分区退出之后,该标准就处在数列的中档地点。这么些可以称作分区(partition)操作;

递归地(recursive)把小于基准值成分的子数列和大于基准值成分的子数列排序。

  JavaScript代码达成:

 

复制代码

 1 //方法一

 2 function quickSort(array, left, right) {

 3     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {

 4         if (left < right) {

 5             var x = array[right], i = left - 1, temp;

 6             for (var j = left; j <= right; j++) {

 7                 if (array[j] <= x) {

 8                     i++;

 9                     temp = array[i];

10                     array[i] = array[j];

11                     array[j] = temp;

12                 }

13             }

14             quickSort(array, left, i - 1);

15             quickSort(array, i + 1, right);

16         };

17     } else {

18         return 'array is not an Array or left or right is not a number!';

19     }

20 }  

21 var aaa = [3, 5, 2, 9, 1];

22 quickSort(aaa, 0, aaa.length - 1);

23 console.log(aaa);

24 

25 

26 //方法二

27 var quickSort = function(arr) {

28   if (arr.length <= 1) { return arr; }

29   var pivotIndex = Math.floor(arr.length / 2);

30   var pivot = arr.splice(pivotIndex, 1)[0];

31   var left = [];

32   var right = [];

33   for (var i = 0; i < arr.length; i++){

34     if (arr[i] < pivot) {

35       left.push(arr[i]);

36     } else {

37       right.push(arr[i]);

38     }

39   }

40   return quickSort(left).concat([pivot], quickSort(right));

41 };

复制代码

3)算法深入分析

 

顶级状态:T(n卡塔尔国 = O(nlogn卡塔尔国

最差情状:T(nState of Qatar = O(n2State of Qatar

平均意况:T(n卡塔尔 = O(nlogn卡塔尔

六、堆排序

1)算法简单介绍

 

  堆排序(Heapsort)是支使用堆这种数据布局所设计的生龙活虎种排序算法。堆叠是叁个像样完全二叉树的协会,并同不平时间知足聚积的性质:即子结点的键值或索引总是小于(或然高于)它的父节点。

 

2)算法描述和达成

 

  具体算法描述如下:

 

将开头待排序关键字类别(Tucson1,索罗德2....哈弗n卡塔尔(قطر‎营造设成大顶堆,此堆为发端的冬日区;

将堆顶成分Murano[1]与最后叁个成分CR-V[n]换到,那时候收获新的冬日区(福睿斯1,奥迪Q72,......Rubiconn-1State of Qatar和新的有序区(Rn卡塔尔国,且满意XC90[1,2...n-1]<=R[n];

鉴于沟通后新的堆顶Sportage[1]大概违反堆的性质,因此要求对当前严节区(大切诺基1,讴歌ZDX2,......宝马X5n-1State of Qatar调解为新堆,然后再一次将Sportage[1]与冬天区最终二个成分交流,拿到新的冬季区(QX561,中华V2....昂科雷n-2State of Qatar和新的有序区(哈弗n-1,HavalnState of Qatar。不断重复此进度直到有序区的成分个数为n-1,则整个排序进程做到。

  JavaScript代码达成:

 

复制代码

 1 /*方法求证:堆排序

 2 @param  array 待排序数组*/            

 3 function heapSort(array) {

 4     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {

 5         //建堆

 6         var heapSize = array.length, temp;

 7         for (var i = Math.floor(heapSize / 2); i >= 0; i--) {

 8             heapify(array, i, heapSize);

 9         }

10         

11         //堆排序

12         for (var j = heapSize - 1; j >= 1; j--) {

13             temp = array[0];

14             array[0] = array[j];

15             array[j] = temp;

16             heapify(array, 0, --heapSize);

17         }

18     } else {

19         return 'array is not an Array!';

20     }

21 }

22 /*措施求证:维护堆的性质

23 @param  arr 数组

24 @param  x   数组下标

25 @param  len 堆大小*/

26 function heapify(arr, x, len) {

27     if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {

28         var l = 2 * x, r = 2 * x + 1, largest = x, temp;

29         if (l < len && arr[l] > arr[largest]) {

30             largest = l;

31         }

32         if (r < len && arr[r] > arr[largest]) {

33             largest = r;

34         }

35         if (largest != x) {

36             temp = arr[x];

37             arr[x] = arr[largest];

38             arr[largest] = temp;

39             heapify(arr, largest, len);

40         }

41     } else {

42         return 'arr is not an Array or x is not a number!';

43     }

44 }

复制代码

3)算法分析

 

最棒状态:T(n卡塔尔 = O(nlogn卡塔尔

最差景况:T(n卡塔尔国 = O(nlognState of Qatar

平均境况:T(nState of Qatar = O(nlogn卡塔尔(قطر‎

七、归拢列排在一条线序

1)算法简单介绍

 

  合并列排在一条线序是树立在统意气风发操作上的风流罗曼蒂克种有效的排序算法。该算法是选择分治法(Divide and Conquer)的多少个卓殊精华的应用。归总列排在一条线序是豆蔻梢头种和谐的排序方法。将已板上钉钉的子类别合併,获得完全有序的队列;即先使各类子序列有序,再使子连串段间有序。若将七个不改变表合併成叁个一直以来表,称为2-路归拢。

 

2)算法描述和促成

 

  具体算法描述如下:

 

把长度为n的输入种类分成三个长度为n/2的子类别;

对这三个子系列分别选择归总列排在一条线序;

将八个排序好的子类别合并成三个终极的排序类别。

  JavaScript代码完成:

 

复制代码

 1 function mergeSort(array, p, r) {

 2     if (p < r) {

 3         var q = Math.floor((p + r) / 2);

 4         mergeSort(array, p, q);

 5         mergeSort(array, q + 1, r);

 6         merge(array, p, q, r);

 7     }

 8 }

 9 function merge(array, p, q, r) {

10     var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0;

11     for (var i = 0; i < n1; i++) {

12         left[i] = array[p + i];

13     }

14     for (var j = 0; j < n2; j++) {

15         right[j] = array[q + 1 + j];

16     }

17     left[n1] = right[n2] = Number.MAX_VALUE;

18     for (var k = p; k <= r; k++) {

19         if (left[m] <= right[n]) {

20             array[k] = left[m];

21             m++;

22         } else {

23             array[k] = right[n];

24             n++;

25         }

26     }

27 }

复制代码

3)算法剖判

 

拔尖状态:T(n卡塔尔 = O(n卡塔尔国

最差情状:T(n卡塔尔 = O(nlogn卡塔尔

平均意况:T(n卡塔尔国 = O(nlogn卡塔尔(قطر‎

八、桶排序

1)算法简单介绍

 

  桶排序 (巴克et sort)的劳作的法规:若是输入数据信守均匀布满,将数据分到有限数量的桶里,每个桶再分别排序(有超大大概再使用别的排序算法或是以递归模式连续利用桶排序举行排序)。

 

2)算法描述和落到实处

 

  具体算法描述如下:

 

设置叁个定量的数组当做空桶;

遍历输入数据,何况把数量贰个三个停放对应的桶里去;

对各种不是空的桶实行排序;

未有是空的桶里把排好序的数据拼接起来。

  JavaScript代码实现:

 

复制代码

 1 /*方法求证:桶排序

 2 @param  array 数组

 3 @param  num   桶的数量*/

 4 function bucketSort(array, num) {

 5     if (array.length <= 1) {

 6         return array;

 7     }

 8     var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0;

 9     num = num || ((num > 1 && regex.test(num)) ? num : 10);

10     for (var i = 1; i < len; i++) {

11         min = min <= array[i] ? min : array[i];

12         max = max >= array[i] ? max : array[i];

13     }

14     space = (max - min + 1) / num;

15     for (var j = 0; j < len; j++) {

16         var index = Math.floor((array[j] - min) / space);

17         if (buckets[index]卡塔尔国 {   //  非空桶,插入排序

18             var k = buckets[index].length - 1;

19             while (k >= 0 && buckets[index][k] > array[j]) {

20                 buckets[index][k + 1] = buckets[index][k];

21                 k--;

22             }

23             buckets[index][k + 1] = array[j];

24         } else {    //空桶,初始化

25             buckets[index] = [];

26             buckets[index].push(array[j]);

27         }

28     }

29     while (n < num) {

30         result = result.concat(buckets[n]);

31         n++;

32     }

33     return result;

34 }

复制代码

3)算法剖判

 

  桶排序最棒状态下行使线性时间O(nState of Qatar,桶排序的岁月复杂度,取决与对各样桶里面数据开展排序的时间复杂度,因为其余一些的时间复杂度都为O(n卡塔尔国。很显眼,桶划分的越小,各类桶之间的数目越少,排序所用的日子也会越少。但对应的空间消耗就能够增大。

 

九、计数排序

1)算法简要介绍

 

  计数排序(Counting sort卡塔尔国是后生可畏种协和的排序算法。计数排序使用一个额外的数组C,当中第i个要素是待排序数组A中值等于i的要素的个数。然后依据数组C来将A中的成分排到准确的地点。它不能不对整数实行排序。

 

2)算法描述和促成

 

  具体算法描述如下:

 

找寻待排序的数组中最大和微小的因素;

计算数组中各样值为i的因素现身的次数,存入数组C的第i项;

对富有的计数累积(从C中的第一个要素伊始,每豆蔻梢头项和前生机勃勃项相加);

反向填充目的数组:将各样成分i放在新数组的第C(iState of Qatar项,每放叁个要素就将C(i卡塔尔减去1。

  JavaScript代码达成:

 

复制代码

 1 function countingSort(array) {

 2     var len = array.length, B = [], C = [], min = max = array[0];

 3     for (var i = 0; i < len; i++) {

 4         min = min <= array[i] ? min : array[i];

 5         max = max >= array[i] ? max : array[i];

 6         C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;

 7     }

 8     for (var j = min; j < max; j++) {

 9         C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);

10     }

11     for (var k = len - 1; k >=0; k--) {

12         B[C[array[k]] - 1] = array[k];

13         C[array[k]]--;

14     }

15     return B;

16 }

笔试面试常常涉及种种算法,本文简单介绍常用的局地算法,并用JavaScript达成。 1、插入排序 1)算法简单介绍 插...

那应该是生机勃勃道新归入的题。意思是给您三个非负整数num,对于0到num那(num+1State of Qatar个整数,求出每种数用二进制表示时1的个数。

解题思路

那道题咋黄金年代看还挺轻便的,无非是:

  • 达成一个办法 countBit,对大肆非负整数 n,总结它的二进制数中“1”的个数
  • 循环 i 从 0 到 num,求 countBit(i),将值放在数组中回到。

JavaScript中,计算 countBit 能够取巧:

function countBit(n){ return n.toString(2).replace(/0/g,"").length; }

1
2
3
function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}

上边的代码里,大家直接对 n 用 toString(2State of Qatar转成二进制表示的字符串,然后去掉其中的0,剩下的正是“1”的个数。

然后,大家写一下完完全全的次序:

版本1

function countBit(n){ return n.toString(2).replace(/0/g,'').length; } function countBits(nums){ var ret = []; for(var i = 0; i <= nums; i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
function countBit(n){
   return n.toString(2).replace(/0/g,'').length;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上边这种写法拾壹分别得到益,好处是 countBit 利用 JavaScript 语言特色完结得特别精短,坏处是假设今后要将它改写成其余语言的本子,就有希望懵B了,它不是很通用,何况它的质量还取决于Number.prototype.toString(2卡塔尔国 和 String.prototype.replace 的贯彻。

于是为了追求更加好的写法,大家有需求考虑一下 countBit 的通用达成法。

我们说,求三个整数的二进制表示中 “1” 的个数,最平时的本来是三个 O(logN)的法门:

function countBit(n){ var ret = 0; while(n > 0){ ret += n & 1; n >>= 1; } return ret; }

1
2
3
4
5
6
7
8
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}

于是我们有了版本2

那般完结也很简单不是啊?但是这样实现是不是最优?建议此处思忖10秒钟再往下看。


关于作者:十年踪迹

图片 1

月影,奇舞团上校,热爱前端开荒,JavaScript 程序员大器晚成枚,能写代码也能打杂卖萌说段子。 个人主页 · 笔者的篇章 · 14 ·     

图片 2

AC代码(C++):

更快的 countBit

上一个本子的 countBit 的年月复杂度已然是 O(logN)了,难道还能越来越快吧?当然是能够的,大家无需去看清每一人是否“1”,也能领会n 的二进制中有多少个“1”。

有一个门道,是基于以下一个定律:

  • 对此自由 n, n ≥ 1,犹如下等式创设:

countBit(n & (n - 1)) === countBit(n) - 1

1
countBit(n & (n - 1)) === countBit(n) - 1

那些比较轻松精通,大家只要想转手,对于自由 n,n – 1 的二进制数表示正巧是 n 的二进制数的最末七个“1”退位,因而 n & n – 1 刚好将 n 的最末壹个人“1”消去,比如:

  • 6 的二进制数是 110, 5 = 6 – 1 的二进制数是 101,6 & 5 的二进制数是 110 & 101 == 100
  • 88 的二进制数是 1011000,87 = 88 – 1 的二进制数是 1010111,88 & 87 的二进制数是 1011000 & 1010111 == 1010000

于是乎,大家有了多少个更加快的算法:

版本3

function countBit(n){ var ret = 0; while(n > 0){ ret++; n &= n - 1; } return ret; } function countBits(nums){ var ret = []; for(var i = 0; i <= nums; i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret++;
        n &= n - 1;
    }
    return ret;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面的 countBit(88) 只循环 3 次,而“版本2”的 countBit(88) 却要求循环 7 次。

优化到了这几个水平,是不是100%都终止了啊?从算法上来讲好似早已然是十二万分了?真的吗?再给我们30 秒时间考虑一下,然后再往下看。


打赏支持小编写出更加多好作品,谢谢!

任选生龙活虎种支付办法

图片 3 图片 4

1 赞 7 收藏 2 评论

class Solution {
public:
    vector<int> countBits(int num) {
        if (num <= 0)
            return vector<int>(1, 0);

        vector<int> ret(num+1, 0);
        int i = 0;
        int half = 0;

        for (i = 1; i <= num; ++i)
        {
            //the number of 1's in half equals the number of 1's in i except the right-most bit in i 
            half = i >> 1;
            if (i % 2 == 0)//the right-most bit in i is 0
                ret[i] = ret[half];
            else//the right-most bit in i is 1
                ret[i] = ret[half] + 1;
        }

        return ret;
    }
};
上一篇:H5游戏开荒:一笔画 下一篇:没有了

Copyright © 2015-2019 http://www.carrefourstation.com. 澳门新莆京手机网站-新蒲京娱乐场有限公司 版权所有