資訊專欄INFORMATION COLUMN
摘要：劍指系列刷題第一篇題目來源數(shù)組中數(shù)字出現(xiàn)的次數(shù)大家可以去測試一下自己的代碼博主碼云鏈接文章目錄前言題目描述解題思路解題代碼前言這是劍指系列刷題第一篇文章，大家可以互相學(xué)習(xí)一下。其中的兩個單身狗是和。
??《劍指offer》系列刷題——第一篇 ??
題目來源：數(shù)組中數(shù)字出現(xiàn)的次數(shù)（大家可以去測試一下自己的代碼）
?? 博主碼云gitee鏈接：https://gitee.com/byte-binxin ??
這是《劍指offer》系列刷題第一篇文章，大家可以互相學(xué)習(xí)一下。
題目描述
一個整型數(shù)組 nums 里除兩個數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。
事例1：
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
事例2：
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
題目要求：
/** * Note: The returned array must be malloced, assume caller calls free(). */解題思路
此題要求我們在一個數(shù)組中除兩個數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次，讓我們找到兩個只出現(xiàn)一次的數(shù)字。這題對時間復(fù)雜度和空間復(fù)雜度都有要求?？臻g復(fù)雜度是O(1)限制我們不能夠額外開辟一塊大于O(n)的空間。
這題我們考慮采用異或來解決這題，什么是異或？
兩個數(shù)異或的結(jié)果是把他們的二進制數(shù)中對應(yīng)的二進制位進行異或，相異為1，相同0。
例：1和2異或
1^2
1 00000000 00000000 00000000 00000001
2 00000000 00000000 00000000 00000010
:: 00000000 00000000 00000000 00000011
1^2 = 3
a ^ b = b ^ a
a ^ 0 = a
開始解題：
第二步
將這個數(shù)拆分開。
代碼實現(xiàn)
int* singleNumbers(int* nums, int numsSize, int* returnSize){ int t = 0; //第一步 //將數(shù)組中所用的數(shù)字與x異或一遍 //得到的結(jié)果就是兩個單身狗異或的結(jié)果 int i = 0; for (i = 0; i < numsSize; i++) { t ^= nums[i]; } //第二步 //分組 //分組前準(zhǔn)備 找到t的二級制數(shù)中為1的那一位，記錄為m //為什么找為1的那一位呢？ //因為1就說明兩個單身狗這一位是不同的 int m = 0; while (m<32) { if (t&(1<<m)) { break; } m++; } //正式分組 將m位為1的分到一組，為0的分到另一組 int x = 0; int y = 0; for (i = 0; i < numsSize; i++) { if (nums[i]&(1<<m)) { //組1全部異或 x ^= nums[i]; } else { //組2全部異或 y ^= nums[i]; } } *returnSize = 2; int* returnArray = (int*)malloc(sizeof(int)*2); returnArray[0] = x; returnArray[1] = y; return returnArray;}文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/122326.html
摘要：導(dǎo)航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結(jié)劍指從尾到頭打印鏈表題目詳情輸入一個鏈表的頭節(jié)點，從尾到頭反過來返回每個節(jié)點的值用數(shù)組返回。時間復(fù)雜度方法先反轉(zhuǎn)鏈表并求長度，在將反轉(zhuǎn)后的鏈表數(shù)據(jù)拷貝至數(shù)組中。 ...
摘要：假設(shè)反轉(zhuǎn)對象節(jié)點為，反轉(zhuǎn)指向的結(jié)點為，反轉(zhuǎn)后指向的結(jié)點為首結(jié)點。當(dāng)然也可以根據(jù)棧先進后出的特點，使用棧反轉(zhuǎn)鏈表。 ??前面的話?? 大家好！博主開辟了一個新的專欄—...
??前面的話?? 大家好！這是Java基礎(chǔ)知識與數(shù)據(jù)結(jié)構(gòu)博文的導(dǎo)航帖，收藏我！學(xué)習(xí)Java不迷路！ ?博客主頁：未見花聞的博客主頁 ?歡迎關(guān)注?點贊?收藏??留言? ?本文由未見花聞原創(chuàng)，CSDN首發(fā)！ ?首發(fā)時間：?2021年11月11日? ??堅持和努力一定能換來詩與遠方！ ?參考書籍：?《Java核心技術(shù)卷1》，?《Java核心技術(shù)卷2》，?《Java編程思想》 ?參考在線編程網(wǎng)站：?牛...
閱讀 2152·2021-11-11 16:54
閱讀 1118·2021-10-12 10:12
閱讀 444·2019-08-30 15:43
閱讀 721·2019-08-29 13:15
閱讀 1146·2019-08-29 13:12
閱讀 1597·2019-08-26 12:09
閱讀 1727·2019-08-26 10:24
閱讀 2348·2019-08-26 10:15
