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