【每日刷题】Day77

【每日刷题】Day77

个人主页：开敲

所属专栏：每日刷题

文章目录

1. LCR 159. 库存管理 III - 力扣（LeetCode）

2. LCR 075. 数组的相对排序 - 力扣（LeetCode）

3. 1346. 检查整数及其两倍数是否存在 - 力扣（LeetCode）

1. LCR 159. 库存管理 III - 力扣（LeetCode）

//思路：TopK问题，堆排序。

void Swap(int* x,int* y)

{

    int tmp = *x;

    *x = *y;

    *y = tmp;

}

//向下调整

void AdjustDown(int* arr,int parents,int size)

{

    int child = parents*2+1;

    while(child<size)

    {

        if(child+1<size&&arr[child+1]<arr[child])

            child++;

        if(arr[child]<arr[parents])

            Swap(&arr[child],&arr[parents]);

        else

            break;

        parents = child;

        child = parents*2+1;

    }

}

//堆排序

void HeapSort(int* arr,int size,int cnt)

{

    for(int i = (size-2)/2;i>=0;i--)

    {

        AdjustDown(arr,i,size);

    }

    while(cnt)

    {

        Swap(&arr[0],&arr[size-1]);

        size--;

        cnt--;

        AdjustDown(arr,0,size);

    }

}

int* inventoryManagement(int* stock, int stockSize, int cnt, int* returnSize)

{

//堆排序将cnt个最小的数排到数组最后

    HeapSort(stock,stockSize,cnt);

    int* ans = (int*)malloc(sizeof(int)*stockSize);

    int count = 0;

    for(int i = stockSize-cnt;i<=stockSize-1;i++)

    {

        ans[count++] = stock[i];

    }

    *returnSize = count;

    return ans;

}

2. LCR 075. 数组的相对排序 - 力扣（LeetCode）

//思路：哈希记数+遍历。遍历数组1，将数组1中每个元素出现的次数记录。随后遍历数组2，根据数组2的元素出现顺序将数组1中的元素放入新数组。

int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)

{

    int* ans = (int*)malloc(sizeof(int)*(arr1Size));

    int count = 0;

    int hash[1001] = {0};

    for(int i = 0;i<arr1Size;i++)

    {

        hash[arr1[i]]+=1;//记录数组1每个元素出现的次数

    }

    for(int i = 0;i<arr2Size;i++)

    {

        while(hash[arr2[i]])

        {

            ans[count++] = arr2[i];//遍历数组2，按照数组2的相对顺序放元素

            hash[arr2[i]]--;

        }

    }

    for(int i = 0;i<1001;i++)

    {

        while(hash[i])

        {

            ans[count++] = i;//将数组1中未在数组2中出现的元素放入

            hash[i]--;

        }

    }

    *returnSize = count;

    return ans;

}

3. 1346. 检查整数及其两倍数是否存在 - 力扣（LeetCode）

//思路：排序+遍历判断。将数组排为升序，采用冒泡的方式挨个判断每个元素是否满足题意。注意：这里需要处理元素为负的情况。

void Swap(int* x,int* y)

{

    int tmp = *x;

    *x = *y;

    *y = tmp;

}

//向下调整

void AdjustDown(int* arr,int parents,int size)

{

    int child = parents*2+1;

    while(child<size)

    {

        if(child+1<size&&arr[child+1]>arr[child])

            child++;

        if(arr[child]>arr[parents])

            Swap(&arr[child],&arr[parents]);

        else

            break;

        parents = child;

        child = parents*2+1;

    }

}

//堆排序

void HwapSort(int* arr,int size)

{

    for(int i = (size-2)/2;i>=0;i--)

    {

        AdjustDown(arr,i,size);

    }

    while(size)

    {

        Swap(&arr[0],&arr[size-1]);

        size--;

        AdjustDown(arr,0,size);

    }

}

 

bool checkIfExist(int* arr, int arrSize)

{

    HwapSort(arr,arrSize);//排序

    for(int i = 0;i<arrSize-1;i++)

    {

        for(int j = i+1;j<arrSize;j++)

        {

            if(arr[j]==2*arr[i]||(arr[j]<0&&arr[i]<0&&arr[i]==2*arr[j]))//遍历判断每个元素是否满足题意，需要处理元素为负的情况。

                return true;

        }

    }

    return false;

}