时间戳

首页 > 解决方案 > 计算 2 个数组中的元素 (GFG)

python - 计算 2 个数组中的元素 (GFG)

问题描述

我正在研究一个GFG 问题

问题：

给定两个未排序的数组 arr1[] 和 arr2[]。它们可能包含重复项。对于 arr1[] 中的每个元素，在数组 arr2[] 中计数小于或等于它的元素。

示例 1：

输入：

m = 6，n = 6

arr1[] = {1,2,3,4,7,9} arr2[] = {0,1,2,1,1,4}

输出：4 5 5 6 6 6

说明：第二个数组中小于等于1、2、3、4、7、9的元素个数分别为4、5、5、6、6、6

示例 2：

输入：

m = 5，n = 7

arr1[] = {4 8 7 5 1}

arr2[] = {4,48,3,0,1,1,5}

输出：5 6 6 6 3

你的任务： 完成函数 countEleLessThanOrEqual()，它接受两个数组 arr1[]、arr2[]、m 和 n 作为输入，并返回一个包含所需结果的数组（每个 arr2 中小于或等于它的元素计数arr1 中的元素，其中第 i 个输出表示 arr1 中第 i 个元素的计数。）

预期时间复杂度：O((m + n) * log n)。

预期辅助空间：O(1)。

约束： 1<=m,n<=10^5 1<=arr1[i],arr2[j]<=10^5

我的蟒蛇解决方案：

def countEleLessThanOrEqual(arr1,n1,arr2,n2):
    #returns the required output
    
    res=[]
    
    arr2.sort()
    
    for i in range(n1):
        search=arr1[i]
        
        count=0
        start=0
        end=n2-1
        
        while(start<=end):
            
            mid = int(start+(end-start)/2)
            
            if search==arr2[mid]:
                start=mid+1
            
            elif search>arr2[mid]:
                start=mid+1
            
            elif search<arr2[mid]:
                end=mid-1
        
        count=end+1   
        res.append(count)
        
    return res

当我提交它时，它给了我 TLE 错误，即使我的解决方案类似于社论中发布的解决方案：

编辑解决方案：

# python implementation of For each element in 1st 
# array count elements less than or equal to it
# in 2nd array

# function returns the index of largest element 
# smaller than equal to 'x' in 'arr'. For duplicates
# it returns the last index of occurrence of required
# element. If no such element exits then it returns -1
def bin_search(arr, n, x):
    
l = 0
h = n - 1
while(l <= h):
    mid = int((l + h) / 2)
    # if 'x' is greater than or equal to arr[mid], 
    # then search in arr[mid + 1...h]
    if(arr[mid] <= x):
    l = mid + 1;
    else:
    # else search in arr[l...mid-1]
    h = mid - 1
# required index
return h

# function to count for each element in 1st array,
# elements less than or equal to it in 2nd array
def countElements(arr1, arr2, m, n):
# sort the 2nd array
arr2.sort()

# for each element in first array
for i in range(m):
    # last index of largest element 
    # smaller than or equal to x
    index = bin_search(arr2, n, arr1[i])
    # required count for the element arr1[i]
    print(index + 1)

# driver program to test above function
arr1 = [1, 2, 3, 4, 7, 9]
arr2 = [0, 1, 2, 1, 1, 4]
m = len(arr1)
n = len(arr2)
countElements(arr1, arr2, m, n)

# This code is contributed by Aditi Sharma

标签： pythonarraysbinary-search

解决方案

在对第二个数组进行排序后，您可以对它使用二进制搜索：

from bisect import bisect_right

def lowerCount(arr1,arr2):
    arr2.sort()
    return [bisect_right(arr2,v) for v in arr1]


print(*lowerCount([1,2,3,4,7,9],[0,1,2,1,1,4]))      # 4 5 5 6 6 6
print(*lowerCount([4, 8, 7, 5, 1],[4,48,3,0,1,1,5])) # 5 6 6 6 3

排序 arr2 是 O(N log N)，二分查找需要 O(M log N) 总共 O( (N+M) log N )。

如果你不能使用库，你总是可以编写自己的 bisect_right 函数：

def bisect_right(A,x):
    lo,hi  = 0,len(A)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if A[mid] <= x: lo = mid+1
        else:           hi = mid-1
    return hi+1

推荐阅读