企业信息化建设方案 网站,我公司让别人做网站了怎么办,能发朋友圈的网站建设语,温州建校特种作业人员查询题目
给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
现定义函数 greaterCount #xff0c;使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。
你需要使用 n 次操作#xff0c;将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操…题目
给你一个下标从 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 然后再对arr1arr2通过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
