c語言苦手 malloc相關問題求解

c leetcode malloc

leooel97895750 2022-10-21 23:08:49 ‧ 1287 瀏覽

分享至

這是leetcode Contains Duplicate的問題
https://leetcode.com/problems/contains-duplicate/
我用hashtable的方式來解
但不懂malloc那行為什麼要malloc
請求各位大神解答
我原本要直接宣告一個struct直接用但會報錯

另外想問malloc目前只想得到在不知道陣列長度時可以使用
有什麼其他情況也常用的嗎?

還有如果是目前的解法要怎麼free呢?

struct Data{
	int val;
	int empty;
	struct Data *link;
};


int containsDuplicate(int* nums, int numsSize) {

    // 建立長度為997的hashtable
    struct Data Hashtable[997];
    
    // 初始化
    for(int i=0;i<997;i++){
    	Hashtable[i].empty = 1;
    	Hashtable[i].link = NULL;
    }
    
    // 尋訪陣列
    for(int i=0;i<numsSize;i++){
        
        if(Hashtable[hash(nums[i])].empty == 1){
		    Hashtable[hash(nums[i])].val = nums[i];
		    Hashtable[hash(nums[i])].empty = 0;
        }
        else if(Hashtable[hash(nums[i])].empty == 0){
            // 重複則回傳
		    if(Hashtable[hash(nums[i])].val == nums[i]){
                return 1;
            }
			
            // 碰撞但非重複;
            struct Data *prev = &Hashtable[hash(nums[i])];

            // 往深層尋找
            while(prev->link != NULL)
            {
                prev = prev->link;
                // 若重複則回傳
                if(prev->val == nums[i])
                    return 1;
            }
            
            // 在最深層新增一個node
            struct Data *current = malloc(sizeof(Hashtable[hash(nums[i])]));
            current->link = NULL;
            current->val = nums[i];
            prev->link = current;

        }
    }
    return 0;
}

int hash(int number)    //get hash value
{
	return abs(number%997);
}

tryit iT邦研究生 4 級 ‧ 2022-10-22 01:34:00 檢舉

誒，可以貼個題目網址嗎?

leooel97895750 iT邦新手 5 級 ‧ 2022-10-22 01:50:57 檢舉

貼了，若陣列有重複值回傳true，雖然題目可能不是這麼重要

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

2 個回答

淺水員

iT邦大師 6 級 ‧ 2022-10-22 02:37:56

最佳解答

但不懂malloc那行為什麼要malloc
我原本要直接宣告一個struct直接用但會報錯

如果是一般宣告變數，例如 struct Data foo;
這個 foo 所占用的記憶體空間是編譯時就固定了（這時候還沒執行）
所以這種方式無法在執行中根據狀況增加儲存空間

當需要在執行中根據狀況增加儲存空間時
必須採用動態宣告
malloc 就是在執行程式時跟作業系統要記憶體的

還有如果是目前的解法要怎麼free呢?

沒測試過，大概是這樣

// 釋放動態宣告的記憶體
for (int i = 0; i < 997; i++) {
    struct Data *current, *temp;
    current = Hashtable[i].link;
    while (current != NULL) {
        temp = current;
        current = current->link;
        free(temp);
    }
}

最後我想說，這題感覺先排序就可以判斷有沒有重複了
排序法的時間複雜度可以穩定在 nLog(n)
而 hashtable 要看運氣，運氣不好會很慢