今天刷題之前先打個廣告java技術(shù)交流群，群號：130031711隶糕，歡迎各位踴躍加入冈在。平時聊天吹水或者技術(shù)交流倒慧，問題探討啥的都可以。
然后開始今天的刷題包券。

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

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

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

思路：首先題目不難猛计，我記得只出現(xiàn)一次的數(shù)字1是只有一個數(shù)字是單獨出現(xiàn)的，所以用的位運(yùn)算異或^.一樣的數(shù)字會消下去爆捞。最后剩下的是求的數(shù)字奉瘤。但是現(xiàn)在的問題是這個題兩個出現(xiàn)一次的數(shù)字。煮甥。不考慮空間復(fù)雜度就是新建數(shù)組毛好，下標(biāo)代替數(shù)值望艺，出現(xiàn)兩次是2，出現(xiàn)一次是1肌访。最后求出是1的兩個找默。或者說用set吼驶，沒出現(xiàn)過的add惩激。出現(xiàn)過的remove，最后s不過既然題目說了常數(shù)空間蟹演，我還是再想想吧风钻。說實話，我感覺還是要二進(jìn)制運(yùn)算酒请，最后也能算出兩個數(shù)異或的結(jié)果骡技，重點是我想不出來要怎么把這兩個數(shù)分開呢？
我有一個大膽的想法羞反，異或出來的結(jié)果如果有1布朦，則說明兩個數(shù)這個位上一個是0一個是1（這句話可能有點廢話，但是肯定要說明白昼窗，）而且兩個數(shù)異或只要不是相同的數(shù)字一定會有1的存在是趴。所以這里只要單獨吧這個位數(shù)是1的提出來異或。這個位數(shù)是0的也提出來異或澄惊。最終得到的兩個結(jié)果就會是兩個單獨的值（因為別的數(shù)異或也是成對出現(xiàn)唆途，最終還是0）。至于判斷一個數(shù)字的二進(jìn)制的某一位是1還是0我是百度出來的（這塊確實是知識盲區(qū)掸驱，做起來都要依靠百度肛搬，不直接看題解就是我最后的倔強(qiáng)了，哈哈）毕贼。
在這里繼續(xù)表白發(fā)這個帖子的大大（csdn 上的滚婉，我順手點贊關(guān)注了，哈哈）帅刀，然后我貼出這個判斷的方法：

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

class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum ^= i;
        }
        
        int n = 0;
        //找出一個是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};
    }
}

其實我一直都有自知之明嘲恍，而且還恬不要臉的承認(rèn)，二進(jìn)制位運(yùn)算我是真的差雄驹，給我時間我慢慢能理明白是怎么回事佃牛，但是讓我自己想思路之類的真的很折磨，再次感謝我上面截圖的那個大大發(fā)的技術(shù)貼医舆。然后咱們說回來俘侠，這個題其實思路我是差不多想的挺好的，但是寫的時候也是很麻煩蔬将，單獨說這個找出第一個是1的位數(shù)我就不斷在控制臺打印和修改爷速，就這個括號都是提交了兩次才修改對的。
這么說吧霞怀，我感覺這個題不難惫东，就是思路問題，但是對于我而言比較困難毙石，因為不敢確定廉沮。我一直想著有空補(bǔ)補(bǔ)二進(jìn)制運(yùn)算，但是也一直沒空胁黑。真的是工作中接觸不到废封，而且還有是不知道從哪里補(bǔ)起。單純的或與異或我都知道丧蘸，但是就是在題目中不會下意識的去想漂洋。這個就很煩躁啊力喷！哎刽漂，先這樣吧，自省完繼續(xù)刷題了弟孟。

丑數(shù)2

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

示例:
輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數(shù)庭猩。
說明:
1 是丑數(shù)。
n 不超過1690陈症。

思路：其實這個題我記得我是做過的蔼水，好像是丑數(shù)1的時候，那時候我用了最笨的一種方法录肯，就是先算平方差趴腋，然后挨個除，被不是2,3,5除盡就pass。不過后來我記得我看了性能排行第一的代碼优炬，是有什么算法的颁井。哎，太久遠(yuǎn)了記不住了蠢护，不提當(dāng)年雅宾，只說這道題了。我覺得知道第幾個丑數(shù)的前提是從第一個開始一個個列出來應(yīng)該糊余，又仔細(xì)看了下題目秀又，其實除了1,2,3,5剩下的所有丑數(shù)其實都是前面這三個數(shù)乘除得來的。也不知道有沒有用贬芥。算了吐辙，我也不尋思什么算法不算法了，先暴力法試試能不能解決吧蘸劈。

好了昏苏，死去活來擼了不少頭發(fā)終于寫出來了，這個我到底還是沒暴力法威沫。其實是暴力法寫著寫著發(fā)現(xiàn)找到點規(guī)律贤惯。我決定把心里路程好好講講：
首先最開始提到的判斷每個數(shù)是不是丑數(shù)，但是從1開始除一直到平方值太傻了棒掠，丑數(shù)只能是2,3,5組成孵构，其實我們可以直接用已有的丑數(shù)來判斷，所以我的打算是把已經(jīng)求出來的丑數(shù)列出來烟很，新的數(shù)字從第一個丑數(shù)開始除颈墅，如果除盡了判斷倍數(shù)是不是也在丑數(shù)里，如果是的話肯定是丑數(shù)雾袱。但是因為要判斷倍數(shù)是不是也在丑數(shù)里恤筛，所以這里就要用到了contains。我開始打算用set芹橡。但是用著用著毒坛，發(fā)現(xiàn)其實這個是有規(guī)律的，所以又開始沉迷于找規(guī)律林说。然后找規(guī)律的過程中真的發(fā)現(xiàn)規(guī)律了煎殷，所以就大改代碼投放，set也刪了菠红，反正是實現(xiàn)了，哈哈贷祈，我先貼代碼度秘，大家可以看一下，性能超過百分之九十七：

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

感覺比我最開始的每個都判斷要好多了，這樣是直接找出答案的垢乙，不過要是沒一開始的思路和測試也想不出這個锨咙，然后中間的坑就是if最小值是某倆數(shù)相乘這塊，因為本來我是用if-else的追逮。但是用著以后測試案例發(fā)現(xiàn)結(jié)果不是預(yù)期的酪刀，控制臺打印每一個元素發(fā)現(xiàn)是6,10,12出現(xiàn)了兩次（我用n=13測試的）。然后再一分析钮孵，23,32.25,52之類的骂倘。所以這里不能用if-else，一定要都if巴席，出現(xiàn)兩個相乘了要兩個都加1历涝。
當(dāng)然寫到這我這個代碼就完成了，至于set的想法我是沒最終實現(xiàn)漾唉，但是我覺得思路也是沒問題荧库，不知道寫出來會不會超時，反正是沒問題的赵刑。不過我就不去實現(xiàn)了分衫，下一題了。
額般此，最后我還是沒忍住看了下性能排行第一的代碼蚪战，差不多一樣的思路，只不過人家是做成了構(gòu)造方法直接把所有的丑數(shù)列出來了恤煞。所以這道題就這么過了屎勘。

H指數(shù)

題目：給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負(fù)整數(shù)）。編寫一個方法居扒，計算出研究者的 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进副。
說明: 如果 h 有多種可能的值这揣，h 指數(shù)是其中最大的那個悔常。

思路：沒有時間空間要求。要么就最傻的一個個判斷给赞』颍或者先排序，再從最高處開始判斷片迅，因為這個題目的意思我覺得我理解的不清楚残邀，不知道思路是不是對的，我先去試試再說柑蛇。
說真的芥挣，這個題不難，就是描述讓我理解不了耻台，一遍遍看題目空免，分析琢磨，我覺得我應(yīng)該要補(bǔ)補(bǔ)語文了粘我。
然后主要抓到兩句：最多h篇被引用了最少h次鼓蜒。h指數(shù)是其中最大的那個。
根據(jù)最多h篇被引用最少h次征字。這兩個最多最少告訴我們邊界都弹。首先我們排序可以通過下標(biāo)知道這之前有多少篇，這之后多少篇匙姜。
然后被引用的次數(shù)是這個元素位置后面有多少個元素（包括當(dāng)前元素）畅厢，所以次數(shù)是數(shù)組總長減去當(dāng)前下標(biāo)（因為包含當(dāng)前的，所以這里數(shù)組總長不用-1）氮昧。
然后這個最多h篇框杜，最少h次，這兩個詞可以判斷篇數(shù)大于次數(shù)袖肥。換言之次數(shù)小于篇數(shù)咪辱，所以有表達(dá)式：次數(shù)<=篇數(shù)（最多最少是可以相等的并且次數(shù)肯定越來越小，所以取第一個結(jié)果就是最大的那個）椎组。于是就有了下面的代碼：

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;
    }
}

這道題真的是考驗理解能力油狂，代碼上不難，我這個性能不是最好的寸癌，我覺得有可能是排序的問題专筷？是不是我手寫排序能好點？算了蒸苇，我直接去看看性能第一的代碼了磷蛹，真的懶得寫排序。溪烤。味咳。
看完性能第一的代碼我自閉了庇勃，我本來以為我是細(xì)節(jié)處理上有點問題，看完發(fā)現(xiàn)我是智商上有問題槽驶。匪凉。。寫的挺好的捺檬，簡潔方便，就是一遍沒看懂贸铜，兩遍還是懵堡纬，，蒿秦，最后我debug了烤镐。。棍鳖。我直接貼代碼：

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] papers = new int[n + 1];
        // 計數(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;
    }
}

首先這個papers是個計數(shù)用的數(shù)組炮叶，總數(shù)肯定是數(shù)組的長度。其實這個h不會大于數(shù)組長度的渡处，其次因為分布不同镜悉，直接計數(shù)每個數(shù)字前面后面的個數(shù)。我貼上調(diào)試的截圖：

papers計數(shù)

然后其實得出的計數(shù)的結(jié)論医瘫，我們從后往前相加侣肄，只要到某一個點，這個個數(shù)不小于下標(biāo)就說明我們找對值了醇份。也就直接返回稼锅。因為這個要取最大的指數(shù)，所以從后往前遍歷就行僚纷。這個想法真的是精巧矩距，因為咱們這里不需要排出數(shù)值的大小，只是為了知道后面多少個元素就行怖竭，所以計數(shù)器的數(shù)組真的思路賊棒锥债！我是第一次接觸這樣計數(shù)排序的方法，驚為天人侵状，反正各種舔赞弥，哈哈~這個辦法我記住了。下一題吧趣兄。

H指數(shù)2

題目：給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負(fù)整數(shù)）绽左，數(shù)組已經(jīng)按照升序排列。編寫一個方法艇潭，計算出研究者的 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。
說明:
如果 h 有多有種可能的值 捍壤，h 指數(shù)是其中最大的那個骤视。
進(jìn)階：
這是 H指數(shù) 的延伸題目，本題中的 citations 數(shù)組是保證有序的鹃觉。
你可以優(yōu)化你的算法到對數(shù)時間復(fù)雜度嗎专酗？

思路：額，題目一點沒變盗扇，只不過增加了進(jìn)階條件祷肯，時間復(fù)雜度有要求了。首先咱們之前的算法是從前往后遍歷疗隶，所以復(fù)雜度是O(n)佑笋，對數(shù)時間復(fù)雜度我第一想法是二分，所以這個題二分也不是不行哈斑鼻，先判斷中間點允青，如果中間點可以滿足則繼續(xù)往前半段判斷，中間點滿足不了往后半段判斷卵沉。我去寫了颠锉。
好了，回來了史汗，我覺得沒啥說的琼掠，就是二分法實現(xiàn)了（雖然我覺得時間復(fù)雜度到不了對數(shù)，但是沒辦法停撞，一說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;
    }
}

然后性能超過百分百了，我去瞅一眼題解戈毒，沒問題的話這道題就這樣了艰猬。
嗯，這道題就這樣了埋市，暫時看題解啥的都沒啥亮點冠桃，上道題的那個計數(shù)排序是亮點但是這個題不適用。
今天的筆記就記到這里了道宅，如果稍微幫到你了記得點個喜歡點個關(guān)注食听。我回盡量每天刷題并且記成筆記的胸蛛，也祝大家工作順順利利，生活健健康康樱报！再打個廣告：java技術(shù)交流群葬项，群號：130031711，歡迎各位踴躍加入迹蛤。