3072. 将元素分配到两个数组中 II

题目

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中严格大于 val 的元素数量。

你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
如果仍然相等，那么将 nums[i] 追加到 arr1 。

连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回整数数组 result 。

示例 1：

输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。

示例 2：

输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。

示例 3：

输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。

提示：

3 <= n <= 10^5
1 <= nums[i] <= 10^9

思路

如果不排序会超时，这个其实跟昨天写的那一篇一样，写一个结构体存一下，然后排序，这样就可以简化搜索
大概这样

typedef struct
{
	int oldIndex;
	int val;
}my_st_t;

排序之后，搜索的时候就可以直接二分查找，从n^2变成nlogn
然后再对arr1，arr2通过oldindex排序后拼接就行了

代码

完整代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int greaterCount(int* arr, int val, int arrsize)
{
    int cnt = 0;
    for (int i = 0; i < arrsize; i++)
    {
        if(arr[i] > val)
        {
            cnt++;
        }
    }
    return cnt;
}
int* resultArray(int* nums, int numsSize, int* returnSize) {
    int* arr1 = (int*)calloc(numsSize, sizeof(int));
    int* arr2 = (int*)calloc(numsSize, sizeof(int));
    int* res = (int*)calloc(numsSize, sizeof(int));
    arr1[0] = (int)nums[0];
    arr2[0] = (int)nums[1];
    int arr1index = 1, arr2index =1;
    for (int i = 2; i < numsSize; i++)
    {
        int res1 = 0;
        int res2 = 0;
        res1 = greaterCount(arr1, nums[i], arr1index);
        res2 = greaterCount(arr2, nums[i], arr2index);

        if(res1 == res2)
        {
            if(arr1index > arr2index)
            {
                arr2[arr2index] = nums[i];
                arr2index++;
            }
            else
            {
                arr1[arr1index] = nums[i];
                arr1index++;
            }
        }
        else if(res1 > res2)
        {
            arr1[arr1index] = nums[i];
            arr1index++;
        }
        else if(res1 < res2)
        {
            arr2[arr2index] = nums[i];
            arr2index++;
        }
    }
    int resindex = 0;
    for (int i = 0; i < arr1index; i++,resindex++)
    {
        res[resindex] = arr1[i];
    }
    for (int i = 0; i < arr2index; i++,resindex++)
    {
        res[resindex] = arr2[i];
    }
    
    (*returnSize) = resindex;
    free(arr1);
    free(arr2);
    return res;
}

int main(void)
{
    int arr[] = {5,14,3,1,2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int returnsize = 0;
    int* res = resultArray(arr, size, &returnsize);
    for (int i = 0; i < returnsize; i++)
    {
        printf("%d ", res[i]);
    }
}

结果

./test
input is : 5 14 3 1 2 
result is : 5 3 1 2 14 

./test
input is : 2 1 3 3 
result is : 2 3 1 3 

./test
size = 12
input is : 22 51 36 312 2344 6123 535 1235 723456 1243 5234 1234 
result is : 22 312 2344 535 723456 1243 51 36 6123 1235 5234 1234