1 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路：

 暴力解法（嵌套循环）

这是一个比较直接的解法，思路就是通过双重循环来判断每个数出现了几次：

• 外层循环用于遍历数组中的每一个元素。
• 内层循环用于统计当前元素在整个数组中出现的次数。
• 如果某个元素只出现一次，就将其存入结果数组 ret 中。
• 最后返回结果数组 ret。

代码：

int* singleNumber(int* nums, int numsSize, int* returnSize){
    // 初始化 returnSize 为 0，表示还没有存储任何结果
    (*returnSize) = 0;
    
    // 动态分配内存，最坏情况下可能需要返回 numsSize 个元素，但实际上只会返回 2 个
    int* ret = malloc(sizeof(int) * numsSize); 
    
    // 定义计数器和循环变量
    int i, j, count;
    
    // 外层循环遍历数���中的每一个元素
    for (i = 0; i < numsSize; i++) {
        count = 0; // 每次外层循环时，将计数器初始化为 0
        
        // 内层循环统计当前元素 nums[i] 出现的次数
        for (j = 0; j < numsSize; j++) {
            if (nums[i] == nums[j]) {
                count++; // 如果发现相同元素，计数器加 1
            }
        }
        
        // 如果当前元素只出现了一次，将其存入结果数组
        if (count == 1) {
            ret[(*returnSize)++] = nums[i];
        }
    }
    
    // 返回包含两个只出现一次的数的结果数组
    return ret;
}

2合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

思路：

1. 初始化：

   • 使用两个指针 p1 和 p2，分别指向 nums1 和 nums2 的起始位置。
   • 创建一个临时数组 sorted，用于存储合并后的有序结果。

2. 合并过程：

   • 使用 while 循环，当 p1 或 p2 未到达各自数组的末尾时，继续合并。
   • 在循环中，比较 nums1[p1] 和 nums2[p2]：
     • 如果 nums1[p1] 较小，则将 nums1[p1] 放入 sorted 中，并移动 p1 指针。
     • 如果 nums2[p2] 较小，则将 nums2[p2] 放入 sorted 中，并移动 p2 指针。
     • 如果 p1 已经到达 nums1 的末尾，则将剩余的 nums2[p2] 依次放入 sorted 中。
     • 如果 p2 已经到达 nums2 的末尾，则将剩余的 nums1[p1] 依次放入 sorted 中。

3. 结果存储：

   • 将 sorted 数组中的元素复制回 nums1，以完成合并

代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
   int p1 = 0, p2 = 0;  // 初始化两个指针，p1 用于 nums1，p2 用于 nums2
int sorted[m + n];   // 创建一个数组 sorted，用于存放合并后的结果
int cur;             // 当前要插入的数字

// 当 p1 或 p2 还没有到达各自数组的末尾时，继续合并
while (p1 < m || p2 < n) {
    // 如果 nums1 已经遍历完（p1 == m），直接取 nums2 的当前元素
    if (p1 == m) {
        cur = nums2[p2++];
    } 
    // 如果 nums2 已经遍历完（p2 == n），直接取 nums1 的当前元素
    else if (p2 == n) {
        cur = nums1[p1++];
    } 
    // 如果 nums1 当前元素小于 nums2 当前元素，则取 nums1 的当前元素
    else if (nums1[p1] < nums2[p2]) {
        cur = nums1[p1++];
    } 
    // 否则，取 nums2 的当前元素
    else {
        cur = nums2[p2++];
    }
    // 将当前元素放入 sorted 数组中
    sorted[p1 + p2 - 1] = cur;  
}

// 将合并后的结果赋值回 nums1
for (int i = 0; i != m + n; ++i) {
    nums1[i] = sorted[i]; 
}

}

思路2：

1. 将 nums2 复制到 nums1 的末尾：

   • 使用一个循环，将 nums2 中的所有元素依次复制到 nums1 中从 m 开始的位置。即 nums1[m + i] = nums2[i]。

2. 对 nums1 进行排序：

   • 使用选择排序算法对 nums1 进行排序。选择排序的基本思想是每次从未排序的部分中找到最小的元素，然后将其放到已排序部分的末尾。
   • 通过嵌套循环，外层循环遍历 nums1 数组的每一个位置，内层循环从当前位置开始，找到未排序部分中的最小元素，并将其与当前位置的元素交换。

代码2：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 将 nums2 中的元素复制到 nums1 后面的空白部分
    for (int i = 0; i < n; i++) {
        nums1[m + i] = nums2[i];  // m 是 nums1 中有效元素的个数，nums2 的元素将从 nums1[m] 开始复制
    }

    // 使用简单的选择排序算法对整个 nums1 数组进行排序
    for (int k = 0; k < m + n; k++) {
        for (int j = k; j < m + n; j++) {
            // 如果 nums1[j] 比 nums1[k] 小，交换这两个元素
            if (nums1[j] < nums1[k]) {  
                int temp = nums1[k];
                nums1[k] = nums1[j];
                nums1[j] = temp;
            }
        }
    }
}

3有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

思路：

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。 先建立一个和题目中大小一样的数组 再让k指向result数组终止位置，这样新数组就会从后往前依次的到原数组中非递减的数字的平方 此时比较左右指针的平方大小，把较大的平方数字放在新数组中，而后原数组中较大的平方数组指针逐渐移动。

代码：

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    //返回的数组大小就是原数组大小
    *returnSize = numsSize;
    //创建两个指针，right指向数组最后一位元素，left指向数组第一位元素
    int right = numsSize - 1;
    int left = 0;

    //最后要返回的结果数组
    int* result = (int*)malloc(sizeof(int) * numsSize);
    int index;
    for(index = numsSize - 1; index >= 0; index--) {
        //左指针指向元素的平方
        int leftnum = nums[left] * nums[left];
        //右指针指向元素的平方
        int rightnum = nums[right] * nums[right];
        //若左指针指向元素平方比右指针指向元素平方大，将左指针指向元素平方放入结果数组。左指针右移一位
        if(leftnum> rightnum) {
            result[index] = leftnum;
            left++;
        } 
        //若右指针指向元素平方比左指针指向元素平方大，将右指针指向元素平方放入结果数组。右指针左移一位
        else {
            result[index] = rightnum;
            right--;
        }
    }
    //返回结果数组
    return result;
}