c语言力扣刷题-数组_力扣c语言刷题

1.

1.给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
 
{
 
        int m = nums1Size;
 
        int n =  nums2Size;
 
        int left = (m + n + 1) / 2;
 
        int right = (m + n + 2) / 2;
 
        return (findKth(nums1,m,n,0, nums2, 0, left) + findKth(nums1,m,n,0, nums2, 0, right)) / 2.0;
 
}
 
    //i: nums1的起始位置 j: nums2的起始位置
 
    int findKth(int *nums1,int m,int n, int i, int*nums2 ,int j, int k)
 
    {
 
        if( i >= m) return nums2[j + k - 1];//nums1为空数组
 
        if( j >= n) return nums1[i + k - 1];//nums2为空数组
 
        if(k == 1){
 
         return nums1[i]<nums2[j]?nums1[i]:nums2[j]; //x>y?x:y如果x大于y则值为x
 
        }
 
        int midVal1 = (i + k / 2 - 1 < m) ? nums1[i + k / 2 - 1] :INT_MAX;
 
        int midVal2 = (j + k / 2 - 1 < n) ? nums2[j + k / 2 - 1] :INT_MAX;//
 
        if(midVal1 < midVal2){
 
            return findKth(nums1,m,n, i + k / 2, nums2, j , k - k / 2);
 
        }else{
 
            return findKth(nums1,m,n, i, nums2, j + k / 2 , k - k / 2);
 
        }        
 
    }

  2.

共有 n 位员工，每位员工都有一个从 0 到 n - 1 的唯一 id 。

给你一个二维整数数组 logs ，其中 logs[i] = [idi, leaveTimei] ：

idi 是处理第 i 个任务的员工的 id ，且

leaveTimei 是员工完成第 i 个任务的时刻。所有 leaveTimei 的值都是 唯一 的。

注意，第 i 个任务在第 (i - 1) 个任务结束后立即开始，且第 0 个任务从时刻 0 开始。

返回处理用时最长的那个任务的员工的 id 。如果存在两个或多个员工同时满足，则返回几人中 最小 的 id 。

示例 1：

输入：n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]

输出：1

解释：

任务 0 于时刻 0 开始，且在时刻 3 结束，共计 3 个单位时间。

任务 1 于时刻 3 开始，且在时刻 5 结束，共计 2 个单位时间。

任务 2 于时刻 5 开始，且在时刻 9 结束，共计 4 个单位时间。

任务 3 于时刻 9 开始，且在时刻 15 结束，共计 6 个单位时间。

时间最长的任务是任务 3 ，而 id 为 1 的员工是处理此任务的员工，所以返回 1 。

示例 2：

输入：n = 26, logs = [[1,1],[3,7],[2,12],[7,17]]

输出：3

解释：

任务 0 于时刻 0 开始，且在时刻 1 结束，共计 1 个单位时间。

任务 1 于时刻 1 开始，且在时刻 7 结束，共计 6 个单位时间。

任务 2 于时刻 7 开始，且在时刻 12 结束，共计 5 个单位时间。

任务 3 于时刻 12 开始，且在时刻 17 结束，共计 5 个单位时间。

时间最长的任务是任务 1 ，而 id 为 3 的员工是处理此任务的员工，所以返回 3 。

示例 3：

输入：n = 2, logs = [[0,10],[1,20]]

输出：0

解释：

任务 0 于时刻 0 开始，且在时刻 10 结束，共计 10 个单位时间。

任务 1 于时刻 10 开始，且在时刻 20 结束，共计 10 个单位时间。

时间最长的任务是任务 0 和 1 ，处理这两个任务的员工的 id 分别是 0 和 1 ，所以返回最小的 0 。

提示：

2 <= n <= 500

1 <= logs.length <= 500

logs[i].length == 2

0 <= idi <= n - 1

1 <= leaveTimei <= 500

idi != idi + 1

leaveTimei 按严格递增顺序排列

 

int hardestWorker(int n, int** logs, int logsSize, int* logsColSize)
 
{
 
        int y=logs[0][0],max=logs[0][1],i=0;
 
        for(int j=1;j<= logsSize-1;j++)
 
        {
 
             int b=logs[j][1]-logs[j-1][1];
 
            if(b>max)
 
            {
 
               max=b;
 
               y=logs[j][0];
 
            }
 
           else if(max==b)
 
           {
 
                max=b;
 
                if(y>logs[j][0])
 
                    y=logs[j][0];
 
           }
 
         
 
        }
 
        return y; 
 
}

2、数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
       * returnSize=2;
 
        int* p = (int*)malloc(sizeof(int)*2);
 
          for(int i=0;i<=numsSize-2;i++)
 
          {
 
               for(int j=i+1;j<=numsSize-1;j++)
 
               {
 
                    if((nums[i]+nums[j])== target)
 
                    {
 
                        p[1]=j;
 
                        p[0]=i;
 
                        break;
 
                    }
 
               }
 
          }
 
          return p;
 
 
 
}