建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
有100盞燈，依次編號(hào)1-100，初始都是關(guān)著的。第1次遍歷，打開(kāi)全部的燈；第2次遍歷，關(guān)掉第2盞、第4盞等被2整除的燈；第3次打開(kāi)被3整除的燈；第i次，對(duì)被i整除的燈做如下操作
成都創(chuàng)新互聯(lián)公司專(zhuān)注于企業(yè)成都全網(wǎng)營(yíng)銷(xiāo)、網(wǎng)站重做改版、祁東網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5高端網(wǎng)站建設(shè)、商城網(wǎng)站定制開(kāi)發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性?xún)r(jià)比高，為祁東等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。
- 如果燈開(kāi)著，就關(guān)掉
- 如果燈關(guān)著，就打開(kāi)
如此交替進(jìn)行，知道100次遍歷完畢，請(qǐng)問(wèn)，還有多少盞燈亮著。
=============================================
數(shù)組統(tǒng)計(jì)分析
原題
給定數(shù)組A，大小為n，數(shù)組元素為1到n的數(shù)字，不過(guò)有的數(shù)字出現(xiàn)了多次，有的數(shù)字沒(méi)有出現(xiàn)。請(qǐng)給出算法和程序，統(tǒng)計(jì)哪些數(shù)字沒(méi)有出現(xiàn)，哪些數(shù)字出現(xiàn)了多少次。能夠在O(n)的時(shí)間復(fù)雜度，O(1)的空間復(fù)雜度要求下完成么？
分析
這個(gè)題目，是有一定技巧的。技巧是需要慢慢積累，待經(jīng)驗(yàn)多了之后，可以靈感或者直覺(jué)，就產(chǎn)生了技巧。如果不知道技巧，那該怎么辦呢？ 在開(kāi)始分析之前，說(shuō)明兩個(gè)問(wèn)題：
- 原數(shù)組是沒(méi)有排序的。如果排序了，很簡(jiǎn)單的。
- O(1)的空間含義，可以使用變量，但不能開(kāi)辟數(shù)組或者map等來(lái)計(jì)數(shù)。
這個(gè)題目，很直接的解法就是兩層遍歷，O(n^2)的復(fù)雜度，O(1)的空間?？臻g滿(mǎn)足了，但是時(shí)間沒(méi)有。 很多類(lèi)似的題目，都會(huì)用XOR的方法，大家仔細(xì)想一下，這個(gè)題目，可以么？或者這個(gè)題目和可以用XOR的題目的差異在哪兒？最直接的就是，每一個(gè)數(shù)字的重復(fù)的次數(shù)是不同的。
還有就是以空間換時(shí)間的方法，例如用hash map或者數(shù)組來(lái)計(jì)數(shù)。時(shí)間滿(mǎn)足了，但是空間沒(méi)有滿(mǎn)足。 那怎樣才能有時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)的算法呢？不能開(kāi)辟新的空間，那么只剩下，重復(fù)利用數(shù)組A。那么該如何利用數(shù)組A呢？
首先，我們介紹一種三次遍歷數(shù)組的方法,我們都考慮數(shù)組從0開(kāi)始：
- 第一次遍歷：對(duì)于每一個(gè)A[i] = A[i] * n
- 第二次遍歷：對(duì)于每一個(gè)i，A[A[i]/n]++
- 第三次遍歷：對(duì)于每一個(gè)i，A[i] % n就是出現(xiàn)次數(shù)
A[i]應(yīng)該出現(xiàn)在A中的A[i]位置，乘以n、再除以n，很容易的來(lái)回變換；第二次遍歷，對(duì)于A[i]本來(lái)所在的位置不斷增1，但絕對(duì)不對(duì)超出n的，那每一個(gè)i出現(xiàn)的次數(shù)，就是A[i]對(duì)n取余。
還有一種兩次遍歷的方法，也是上面的思路：題目中數(shù)組是1到n，為了方便算法考慮，以及數(shù)組存儲(chǔ)方便，我們考慮0-n-1，結(jié)果是相同的。 考慮A[i]，現(xiàn)在位置是i，如果采用A來(lái)計(jì)數(shù)，它的位置應(yīng)該是A[i] % n，找到計(jì)數(shù)位置，該如何處理這個(gè)位置呢？加1么？顯然不可以，這里有一個(gè)技巧，就是加n，有兩個(gè)原因
- 加n可以保證A[i] % n是不變的
- A數(shù)組，最后每一個(gè)元素表示為A[i] = x + k*n，其中x
上面的思路，轉(zhuǎn)換為代碼如下：
新聞標(biāo)題：今日面試題：燈及數(shù)組統(tǒng)計(jì)分析
網(wǎng)站路徑：http://m.fisionsoft.com.cn/article/djheiis.html
