Solved
Easy
Topics
Companies
Hint
Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0]is a list of all distinct integers innums1which are not present innums2.answer[1]is a list of all distinct integers innums2which are not present innums1.
Note that the integers in the lists may be returned in any order.
Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4,6] Output: [[1,3],[4,6]] Explanation: For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3]. For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].
Example 2:
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2] Output: [[3],[]] Explanation: For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3]. Every integer in nums2 is present in nums1. Therefore, answer[1] = [].
Constraints:
1 <= nums1.length, nums2.length <= 1000-1000 <= nums1[i], nums2[i] <= 1000
google 翻譯：
給定兩個 0 索引的整數數組 nums1 和 nums2，傳回大小為 2 的列表答案，其中：
answer[0] 是 nums1 中所有不存在於 nums2 中的不同整數的列表。
answer[1] 是 nums2 中不存在於 nums1 中的所有不同整數的列表。
請注意，列表中的整數可以按任何順序返回
想法一：
把兩陣列排序後刪除重覆的值，
再跑一個迴圈，同時判斷處理後的兩個陣列，
兩陣列值相等，就同時前進，
兩陣列值不相等，就移動小的那邊，並存入結果中
寫法一：
// 刪除重覆的值
int deleteDouble(int *nums, int numsSize) {
int read = 1, write = 1;
while(read < numsSize) {
while(read < numsSize && nums[write-1] == nums[read])
read++;
if (read >= numsSize)
break;
nums[write++] = nums[read++];
}
return write;
}
// 排序用，由小到大
int cmp(const void *d1, const void *d2) {
return *((int *)d1) > *((int *)d2);
}
int** findDifference(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize, int** returnColumnSizes) {
int **result = malloc(sizeof(int *) * 2);
int left = 0, right = 0, c1 = 0, c2 = 0;
// 結果給記憶體
result[0] = malloc(sizeof(int) * nums1Size);
result[1] = malloc(sizeof(int) * nums2Size);
// 先排序
qsort(nums1, nums1Size, sizeof(int), cmp);
qsort(nums2, nums2Size, sizeof(int), cmp);
// 再刪除重覆的值
nums1Size = deleteDouble(nums1, nums1Size);
nums2Size = deleteDouble(nums2, nums2Size);
// 兩陣列都要有值才進判斷
while(left < nums1Size && right < nums2Size) {
if(nums1[left] == nums2[right]) { // 相等，同時前進
left++;
right++;
} else if(nums1[left] > nums2[right]) { // 小的一方前進，並存入結果
result[1][c2++] = nums2[right];
right++;
} else { // nums1[left] < nums2[right] 小的一方前進，並存入結果
result[0][c1++] = nums1[left];
left++;
}
}
// 剩下沒用到的值都要加入結果中
while(left < nums1Size)
result[0][c1++] = nums1[left++];
while(right < nums2Size)
result[1][c2++] = nums2[right++];
//回傳個數設定
*returnSize = 2;
*returnColumnSizes = (int*) malloc(2 * sizeof(int));
(*returnColumnSizes)[0] = c1;
(*returnColumnSizes)[1] = c2;
return result;
}
結果一：
想法二：
題目類別是 hash，用 hash 的解法...
建立一個 hash，把兩陣列的值的個數加到 hash 中。
再用迴圈讀取 hash，加超過兩次的忽略，只有加一次的話，
分別加到各自的結果中
寫法二：
int** findDifference(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize, int** returnColumnSizes) {
int c1=0, c2=0;
int *hash = calloc(2001, sizeof(int)); // 題目指定數值最大只有 -1000 ~ 1000
int **result = malloc(sizeof(int *) * 2);
result[0] = malloc(sizeof(int) * nums1Size);
result[1] = malloc(sizeof(int) * nums2Size);
// 加把一個陣列的個數加到 hash 中（這裡標記成 1）
for(int i=0; i<nums1Size; i++) {
hash[nums1[i] + 1000] = 1;
}
// 另一個陣列加入 hash 前，要先讀出值。
// 有加過就要忽略（這裡標記2），沒加過要標記（這裡標記 -1）
for(int i=0; i<nums2Size; i++) {
if(hash[nums2[i] + 1000] > 0)
hash[nums2[i] + 1000] = 2;
else
hash[nums2[i] + 1000] = -1;
}
// 跑完 hash，把剛標記的分別存入結果中
for(int i=0; i<2001; i++) {
if(hash[i] == 1)
result[0][c1++] = i - 1000;
else if(hash[i] == -1)
result[1][c2++] = i - 1000;
}
*returnSize = 2;
*returnColumnSizes = (int*) malloc(2 * sizeof(int));
(*returnColumnSizes)[0] = c1;
(*returnColumnSizes)[1] = c2;
return result;
}
結果二：
想法三：
hash 設定好之後，改用陣列去查詢 hash 值，而不是跑完全部的 hash
寫法三：
int** findDifference(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize, int** returnColumnSizes) {
int c1=0, c2=0;
int *hash = calloc(2001, sizeof(int)); // 題目指定數值最大只有 -1000 ~ 1000
int **result = malloc(sizeof(int *) * 2);
result[0] = malloc(sizeof(int) * nums1Size);
result[1] = malloc(sizeof(int) * nums2Size);
// 把陣列1的個數加到 hash 中（這裡標記成 1）
for(int i=0; i<nums1Size; i++) {
hash[nums1[i] + 1000] = 1;
}
// 陣列2加入 hash 前，要先讀出值。
// 有加過就要忽略（這裡標記2），沒加過要標記（這裡標記 -1）
for(int i=0; i<nums2Size; i++) {
if(hash[nums2[i] + 1000] > 0)
hash[nums2[i] + 1000] = 2;
else
hash[nums2[i] + 1000] = -1;
}
// 讀取陣列1中的值，查看 hash 是否符合標記 1
for(int i=0; i<nums1Size; i++) {
if(hash[nums1[i] + 1000] == 1) {
hash[nums1[i] + 1000] = 0;
result[0][c1++] = nums1[i];
}
}
// 讀取陣列2中的值，查看 hash 是否符合標記 -1
for(int i=0; i<nums2Size; i++) {
if(hash[nums2[i]+1000] == -1) {
hash[nums2[i] + 1000] = 0;
result[1][c2++] =nums2[i] ;
}
}
*returnSize = 2;
*returnColumnSizes = (int*) malloc(2 * sizeof(int));
(*returnColumnSizes)[0] = c1;
(*returnColumnSizes)[1] = c2;
return result;
}
結果三：
沒有留言:
張貼留言