今天刷題之前先打個(gè)廣告java技術(shù)交流群，群號(hào)：130031711，歡迎各位踴躍加入。平時(shí)聊天吹水或者技術(shù)交流，問(wèn)題探討啥的都可以。
然后開(kāi)始今天的刷題。

只出現(xiàn)一次的數(shù)字2

題目：給定一個(gè)整數(shù)數(shù)組 nums，其中恰好有兩個(gè)元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個(gè)元素。

示例 :
輸入: [1,2,1,3,2,5]
輸出: [3,5]
注意：
結(jié)果輸出的順序并不重要，對(duì)于上面的例子， [5, 3] 也是正確答案。
你的算法應(yīng)該具有線(xiàn)性時(shí)間復(fù)雜度。你能否僅使用常數(shù)空間復(fù)雜度來(lái)實(shí)現(xiàn)？

思路：首先題目不難，我記得只出現(xiàn)一次的數(shù)字1是只有一個(gè)數(shù)字是單獨(dú)出現(xiàn)的，所以用的位運(yùn)算異或^.一樣的數(shù)字會(huì)消下去。最后剩下的是求的數(shù)字。但是現(xiàn)在的問(wèn)題是這個(gè)題兩個(gè)出現(xiàn)一次的數(shù)字。。不考慮空間復(fù)雜度就是新建數(shù)組，下標(biāo)代替數(shù)值，出現(xiàn)兩次是2，出現(xiàn)一次是1。最后求出是1的兩個(gè)?；蛘哒f(shuō)用set，沒(méi)出現(xiàn)過(guò)的add。出現(xiàn)過(guò)的remove，最后s不過(guò)既然題目說(shuō)了常數(shù)空間，我還是再想想吧。說(shuō)實(shí)話(huà)，我感覺(jué)還是要二進(jìn)制運(yùn)算，最后也能算出兩個(gè)數(shù)異或的結(jié)果，重點(diǎn)是我想不出來(lái)要怎么把這兩個(gè)數(shù)分開(kāi)呢？
我有一個(gè)大膽的想法，異或出來(lái)的結(jié)果如果有1，則說(shuō)明兩個(gè)數(shù)這個(gè)位上一個(gè)是0一個(gè)是1（這句話(huà)可能有點(diǎn)廢話(huà)，但是肯定要說(shuō)明白，）而且兩個(gè)數(shù)異或只要不是相同的數(shù)字一定會(huì)有1的存在。所以這里只要單獨(dú)吧這個(gè)位數(shù)是1的提出來(lái)異或。這個(gè)位數(shù)是0的也提出來(lái)異或。最終得到的兩個(gè)結(jié)果就會(huì)是兩個(gè)單獨(dú)的值（因?yàn)閯e的數(shù)異或也是成對(duì)出現(xiàn)，最終還是0）。至于判斷一個(gè)數(shù)字的二進(jìn)制的某一位是1還是0我是百度出來(lái)的（這塊確實(shí)是知識(shí)盲區(qū)，做起來(lái)都要依靠百度，不直接看題解就是我最后的倔強(qiáng)了，哈哈）。
在這里繼續(xù)表白發(fā)這個(gè)帖子的大大（csdn 上的，我順手點(diǎn)贊關(guān)注了，哈哈），然后我貼出這個(gè)判斷的方法：

判斷一個(gè)數(shù)字二進(jìn)制某一位是1還是0

class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum ^= i;
        }
        
        int n = 0;
        //找出一個(gè)是1的位數(shù)
        while(((sum>>n)&1)==0){
            n++;
        }
        int nums1 = 0;
        int nums2 = 0;
        for(int i : nums){
            if(((i>>n)&1)==1){
                nums1^=i;
            }else{
                nums2^=i;
            }
        }
        return new int[]{nums1,nums2};
    }
}

其實(shí)我一直都有自知之明，而且還恬不要臉的承認(rèn)，二進(jìn)制位運(yùn)算我是真的差，給我時(shí)間我慢慢能理明白是怎么回事，但是讓我自己想思路之類(lèi)的真的很折磨，再次感謝我上面截圖的那個(gè)大大發(fā)的技術(shù)貼。然后咱們說(shuō)回來(lái)，這個(gè)題其實(shí)思路我是差不多想的挺好的，但是寫(xiě)的時(shí)候也是很麻煩，單獨(dú)說(shuō)這個(gè)找出第一個(gè)是1的位數(shù)我就不斷在控制臺(tái)打印和修改，就這個(gè)括號(hào)都是提交了兩次才修改對(duì)的。
這么說(shuō)吧，我感覺(jué)這個(gè)題不難，就是思路問(wèn)題，但是對(duì)于我而言比較困難，因?yàn)椴桓掖_定。我一直想著有空補(bǔ)補(bǔ)二進(jìn)制運(yùn)算，但是也一直沒(méi)空。真的是工作中接觸不到，而且還有是不知道從哪里補(bǔ)起。單純的或與異或我都知道，但是就是在題目中不會(huì)下意識(shí)的去想。這個(gè)就很煩躁?。“?，先這樣吧，自省完繼續(xù)刷題了。

丑數(shù)2

題目：編寫(xiě)一個(gè)程序，找出第 n 個(gè)丑數(shù)。丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。

示例:
輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個(gè)丑數(shù)。
說(shuō)明:
1 是丑數(shù)。
n 不超過(guò)1690。

思路：其實(shí)這個(gè)題我記得我是做過(guò)的，好像是丑數(shù)1的時(shí)候，那時(shí)候我用了最笨的一種方法，就是先算平方差，然后挨個(gè)除，被不是2,3,5除盡就pass。不過(guò)后來(lái)我記得我看了性能排行第一的代碼，是有什么算法的。哎，太久遠(yuǎn)了記不住了，不提當(dāng)年，只說(shuō)這道題了。我覺(jué)得知道第幾個(gè)丑數(shù)的前提是從第一個(gè)開(kāi)始一個(gè)個(gè)列出來(lái)應(yīng)該，又仔細(xì)看了下題目，其實(shí)除了1,2,3,5剩下的所有丑數(shù)其實(shí)都是前面這三個(gè)數(shù)乘除得來(lái)的。也不知道有沒(méi)有用。算了，我也不尋思什么算法不算法了，先暴力法試試能不能解決吧。

好了，死去活來(lái)擼了不少頭發(fā)終于寫(xiě)出來(lái)了，這個(gè)我到底還是沒(méi)暴力法。其實(shí)是暴力法寫(xiě)著寫(xiě)著發(fā)現(xiàn)找到點(diǎn)規(guī)律。我決定把心里路程好好講講：
首先最開(kāi)始提到的判斷每個(gè)數(shù)是不是丑數(shù)，但是從1開(kāi)始除一直到平方值太傻了，丑數(shù)只能是2,3,5組成，其實(shí)我們可以直接用已有的丑數(shù)來(lái)判斷，所以我的打算是把已經(jīng)求出來(lái)的丑數(shù)列出來(lái)，新的數(shù)字從第一個(gè)丑數(shù)開(kāi)始除，如果除盡了判斷倍數(shù)是不是也在丑數(shù)里，如果是的話(huà)肯定是丑數(shù)。但是因?yàn)橐袛啾稊?shù)是不是也在丑數(shù)里，所以這里就要用到了contains。我開(kāi)始打算用set。但是用著用著，發(fā)現(xiàn)其實(shí)這個(gè)是有規(guī)律的，所以又開(kāi)始沉迷于找規(guī)律。然后找規(guī)律的過(guò)程中真的發(fā)現(xiàn)規(guī)律了，所以就大改代碼，set也刪了，反正是實(shí)現(xiàn)了，哈哈，我先貼代碼，大家可以看一下，性能超過(guò)百分之九十七：

class Solution {
    public int nthUglyNumber(int n) {
        if(n==1) return 1;
        int v2 = 0;
        int v3 = 0;
        int v5 = 0;
        //第n個(gè)丑數(shù)，先把直到n所有丑數(shù)列出來(lái)
        int[] res = new int[n];
        res[0] = 1;//1是第一個(gè)丑數(shù)
        for(int i = 1;i<n;i++){
            //下一個(gè)丑數(shù)是多少,后面乘的2,3,5是只能是這三個(gè)的倍數(shù)
            int n2 = res[v2] * 2;
            int n3 = res[v3] * 3;
            int n5 = res[v5] * 5;
            res[i] = Math.min(n2,Math.min(n3,n5));
            //這一定要三個(gè)if，不能用if-else。不然2*5和5*2會(huì)算兩次
            if(res[i] == n2) v2++; 
            if(res[i] == n3) v3++;
            if(res[i] == n5) v5++;
        }
        return res[n-1];
    }
}

感覺(jué)比我最開(kāi)始的每個(gè)都判斷要好多了，這樣是直接找出答案的，不過(guò)要是沒(méi)一開(kāi)始的思路和測(cè)試也想不出這個(gè)，然后中間的坑就是if最小值是某倆數(shù)相乘這塊，因?yàn)楸緛?lái)我是用if-else的。但是用著以后測(cè)試案例發(fā)現(xiàn)結(jié)果不是預(yù)期的，控制臺(tái)打印每一個(gè)元素發(fā)現(xiàn)是6,10,12出現(xiàn)了兩次（我用n=13測(cè)試的）。然后再一分析，23,32.25,52之類(lèi)的。所以這里不能用if-else，一定要都if，出現(xiàn)兩個(gè)相乘了要兩個(gè)都加1。
當(dāng)然寫(xiě)到這我這個(gè)代碼就完成了，至于set的想法我是沒(méi)最終實(shí)現(xiàn)，但是我覺(jué)得思路也是沒(méi)問(wèn)題，不知道寫(xiě)出來(lái)會(huì)不會(huì)超時(shí)，反正是沒(méi)問(wèn)題的。不過(guò)我就不去實(shí)現(xiàn)了，下一題了。
額，最后我還是沒(méi)忍住看了下性能排行第一的代碼，差不多一樣的思路，只不過(guò)人家是做成了構(gòu)造方法直接把所有的丑數(shù)列出來(lái)了。所以這道題就這么過(guò)了。

H指數(shù)

題目：給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負(fù)整數(shù)）。編寫(xiě)一個(gè)方法，計(jì)算出研究者的 h 指數(shù)。h 指數(shù)的定義: “h 代表“高引用次數(shù)”（high citations），一名科研人員的 h 指數(shù)是指他（她）的 （N 篇論文中）至多有 h 篇論文分別被引用了至少 h 次。（其余的 N - h 篇論文每篇被引用次數(shù)不多于 h 次。）”

示例:
輸入: citations = [3,0,6,1,5]
輸出: 3
解釋: 給定數(shù)組表示研究者總共有 5 篇論文，每篇論文相應(yīng)的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇論文每篇至少被引用了 3 次，其余兩篇論文每篇被引用不多于 3 次，所以她的 h 指數(shù)是 3。
說(shuō)明: 如果 h 有多種可能的值，h 指數(shù)是其中最大的那個(gè)。

思路：沒(méi)有時(shí)間空間要求。要么就最傻的一個(gè)個(gè)判斷?；蛘呦扰判?，再?gòu)淖罡咛庨_(kāi)始判斷，因?yàn)檫@個(gè)題目的意思我覺(jué)得我理解的不清楚，不知道思路是不是對(duì)的，我先去試試再說(shuō)。
說(shuō)真的，這個(gè)題不難，就是描述讓我理解不了，一遍遍看題目，分析琢磨，我覺(jué)得我應(yīng)該要補(bǔ)補(bǔ)語(yǔ)文了。
然后主要抓到兩句：最多h篇被引用了最少h次。h指數(shù)是其中最大的那個(gè)。
根據(jù)最多h篇被引用最少h次。這兩個(gè)最多最少告訴我們邊界。首先我們排序可以通過(guò)下標(biāo)知道這之前有多少篇，這之后多少篇。
然后被引用的次數(shù)是這個(gè)元素位置后面有多少個(gè)元素（包括當(dāng)前元素），所以次數(shù)是數(shù)組總長(zhǎng)減去當(dāng)前下標(biāo)（因?yàn)榘?dāng)前的，所以這里數(shù)組總長(zhǎng)不用-1）。
然后這個(gè)最多h篇，最少h次，這兩個(gè)詞可以判斷篇數(shù)大于次數(shù)。換言之次數(shù)小于篇數(shù)，所以有表達(dá)式：次數(shù)<=篇數(shù)（最多最少是可以相等的并且次數(shù)肯定越來(lái)越小，所以取第一個(gè)結(jié)果就是最大的那個(gè)）。于是就有了下面的代碼：

class Solution {
    public int hIndex(int[] citations) {
        if(citations.length==0) return 0;
        Arrays.sort(citations);
        for(int i = 0;i<citations.length;i++){
            int count = citations.length-i;
            if(count<=citations[i]){
                return count;
            }
        }
        return 0;
    }
}

這道題真的是考驗(yàn)理解能力，代碼上不難，我這個(gè)性能不是最好的，我覺(jué)得有可能是排序的問(wèn)題？是不是我手寫(xiě)排序能好點(diǎn)？算了，我直接去看看性能第一的代碼了，真的懶得寫(xiě)排序。。。
看完性能第一的代碼我自閉了，我本來(lái)以為我是細(xì)節(jié)處理上有點(diǎn)問(wèn)題，看完發(fā)現(xiàn)我是智商上有問(wèn)題。。。寫(xiě)的挺好的，簡(jiǎn)潔方便，就是一遍沒(méi)看懂，兩遍還是懵，，，最后我debug了。。。我直接貼代碼：

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] papers = new int[n + 1];
        // 計(jì)數(shù)
        for (int c: citations)
            papers[Math.min(n, c)]++;
        // 找出最大的 k
        int k = n;
        for (int s = papers[n]; k > s; s += papers[k])
            k--;
        return k;
    }
}

首先這個(gè)papers是個(gè)計(jì)數(shù)用的數(shù)組，總數(shù)肯定是數(shù)組的長(zhǎng)度。其實(shí)這個(gè)h不會(huì)大于數(shù)組長(zhǎng)度的，其次因?yàn)榉植疾煌?，直接?jì)數(shù)每個(gè)數(shù)字前面后面的個(gè)數(shù)。我貼上調(diào)試的截圖：

papers計(jì)數(shù)

然后其實(shí)得出的計(jì)數(shù)的結(jié)論，我們從后往前相加，只要到某一個(gè)點(diǎn)，這個(gè)個(gè)數(shù)不小于下標(biāo)就說(shuō)明我們找對(duì)值了。也就直接返回。因?yàn)檫@個(gè)要取最大的指數(shù)，所以從后往前遍歷就行。這個(gè)想法真的是精巧，因?yàn)樵蹅冞@里不需要排出數(shù)值的大小，只是為了知道后面多少個(gè)元素就行，所以計(jì)數(shù)器的數(shù)組真的思路賊棒！我是第一次接觸這樣計(jì)數(shù)排序的方法，驚為天人，反正各種舔，哈哈~這個(gè)辦法我記住了。下一題吧。

H指數(shù)2

題目：給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負(fù)整數(shù)），數(shù)組已經(jīng)按照升序排列。編寫(xiě)一個(gè)方法，計(jì)算出研究者的 h 指數(shù)。h 指數(shù)的定義: “h 代表“高引用次數(shù)”（high citations），一名科研人員的 h 指數(shù)是指他（她）的 （N 篇論文中）至多有 h 篇論文分別被引用了至少 h 次。（其余的 N - h 篇論文每篇被引用次數(shù)不多于 h 次。）"

示例:
輸入: citations = [0,1,3,5,6]
輸出: 3
解釋: 給定數(shù)組表示研究者總共有 5 篇論文，每篇論文相應(yīng)的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇論文每篇至少被引用了 3 次，其余兩篇論文每篇被引用不多于 3 次，所以她的 h 指數(shù)是 3。
說(shuō)明:
如果 h 有多有種可能的值 ，h 指數(shù)是其中最大的那個(gè)。
進(jìn)階：
這是 H指數(shù) 的延伸題目，本題中的 citations 數(shù)組是保證有序的。
你可以?xún)?yōu)化你的算法到對(duì)數(shù)時(shí)間復(fù)雜度嗎？

思路：額，題目一點(diǎn)沒(méi)變，只不過(guò)增加了進(jìn)階條件，時(shí)間復(fù)雜度有要求了。首先咱們之前的算法是從前往后遍歷，所以復(fù)雜度是O(n)，對(duì)數(shù)時(shí)間復(fù)雜度我第一想法是二分，所以這個(gè)題二分也不是不行哈，先判斷中間點(diǎn)，如果中間點(diǎn)可以滿(mǎn)足則繼續(xù)往前半段判斷，中間點(diǎn)滿(mǎn)足不了往后半段判斷。我去寫(xiě)了。
好了，回來(lái)了，我覺(jué)得沒(méi)啥說(shuō)的，就是二分法實(shí)現(xiàn)了（雖然我覺(jué)得時(shí)間復(fù)雜度到不了對(duì)數(shù)，但是沒(méi)辦法，一說(shuō)O(logN)第一反應(yīng)就是二分了）。我直接貼代碼：

class Solution {
    public int hIndex(int[] citations) {
        int l = 0;
        int r = citations.length;
        int n = r;
        while(l<r){
            int mid = (r-l)/2+l;
            if(n-mid > citations[mid]){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return n-l;
    }
}

然后性能超過(guò)百分百了，我去瞅一眼題解，沒(méi)問(wèn)題的話(huà)這道題就這樣了。
嗯，這道題就這樣了，暫時(shí)看題解啥的都沒(méi)啥亮點(diǎn)，上道題的那個(gè)計(jì)數(shù)排序是亮點(diǎn)但是這個(gè)題不適用。
今天的筆記就記到這里了，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注。我回盡量每天刷題并且記成筆記的，也祝大家工作順順利利，生活健健康康！再打個(gè)廣告：java技術(shù)交流群，群號(hào)：130031711，歡迎各位踴躍加入。