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