3072. Allocate elements into two arrays II

2024-01-01

字数统计: 778字 | 阅读时长: 4min

topic：

3072. Allocate elements into two arrays II.md
“””

Give you a bidding 1 start、Length n 的整数Array nums 。

Now define function greaterCount ，Make greaterCount(arr, val) 返回Array arr middle Strict val Number of elements。

You need to use n Secondary operation，Will nums 的所有元素分配到两个Array arr1 and arr2 middle。In the first place一Secondary operationmiddle，Will nums[1] Add arr1 。In the first place二Secondary operationmiddle，Will nums[2] Add arr2 。after，In the first place i Secondary operationmiddle：

if greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，Will nums[i] Add arr1 。
if greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，Will nums[i] Add arr2 。
if greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，Will nums[i] Add元素数量较少的Arraymiddle。
if仍然相等，SoWill nums[i] Add arr1 。

连接Array arr1 and arr2 形成Array result 。For example，if arr1 == [1,2,3] and arr2 == [4,5,6] ，So result = [1,2,3,4,5,6] 。

返回整数Array result 。

Exemplary example 1：

enter：nums = [2,1,3,3]
Output：[2,3,1,3]
explain：exist前两Secondary operation后，arr1 = [2] ，arr2 = [1] 。
In the first place 3 Secondary operationmiddle，两个Arraymiddle大于 3 Number of elements都yes零，并and长度相等，therefore，Will nums[3] Add arr1 。
In the first place 4 Secondary operationmiddle，两个Arraymiddle大于 3 Number of elements都yes零，but arr2 Small length，therefore，Will nums[4] Add arr2 。
exist 4 Secondary operation后，arr1 = [2,3] ，arr2 = [1,3] 。
therefore，连接形成的Array result yes [2,3,1,3] 。

Exemplary example 2：

enter：nums = [5,14,3,1,2]
Output：[5,3,1,2,14]
explain：exist前两Secondary operation后，arr1 = [5] ，arr2 = [14] 。
In the first place 3 Secondary operationmiddle，两个Arraymiddle大于 3 Number of elements都yes一，并and长度相等，therefore，Will nums[3] Add arr1 。
In the first place 4 Secondary operationmiddle，arr1 middle大于 1 Number of elements大于 arr2 middle的数量（2 > 1），therefore，Will nums[4] Add arr1 。
In the first place 5 Secondary operationmiddle，arr1 middle大于 2 Number of elements大于 arr2 middle的数量（2 > 1），therefore，Will nums[5] Add arr1 。
exist 5 Secondary operation后，arr1 = [5,3,1,2] ，arr2 = [14] 。
therefore，连接形成的Array result yes [5,3,1,2,14] 。

Exemplary example 3：

enter：nums = [3,3,3,3]
Output：[3,3,3,3]
explain：exist 4 Secondary operation后，arr1 = [3,3] ，arr2 = [3,3] 。
therefore，连接形成的Array result yes [3,3,3,3] 。

hint：

3 <= n <= 10⁵
1 <= nums[i] <= 10⁹

Thought：

initialization：
首先Will nums Array反转，以便我们可以从最后一个元素start处理。这一步exist最初与学长@Angro beatICPCI learned，pop() Compare pop(0) It is much faster。
Will反转后的第一个元素分配给 arr1 and temp1，The second element is allocated to arr2 and temp2。
Iteration processing each element：
use while Traversal nums Array的剩余元素。
For each element，use bisect.bisect_right exist arr1 and arr2 middle找到Compare当前元素小的元素的数量。
Re -uselen(arr1)andlen(arr2)Minus this quantity，得到Compare当前元素大的元素的数量。
然后进行Compare较To。为了use二分查找，therefore我们要保证 arr1 and arr2 yes有序的， Pythonmiddleuse insort() To。
but同时我们要维持一个答案Array，thereforeappendTo。
Merge answer

Code：

import bisect
from typing import List

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        nums = nums[::-1]
        temp = nums.pop()
        arr1 = [temp]
        temp1 = [temp]
        temp = nums.pop()
        arr2 = [temp]
        temp2 = [temp]
        while nums:
            temp = nums.pop()
            # [28] [2]
            index1 = bisect.bisect_right(arr1, temp)
            index2 = bisect.bisect_right(arr2, temp)
            length_1 = len(arr1) - index1
            length_2 = len(arr2) - index2
            if length_1 > length_2:
                bisect.insort(arr1, temp)
                temp1.append(temp)
            elif length_1 < length_2:
                bisect.insort(arr2, temp)
                temp2.append(temp)
            else:
                if len(arr1) > len(arr2):
                    bisect.insort(arr2, temp)
                    temp2.append(temp)
                else:
                    bisect.insort(arr1, temp)
                    temp1.append(temp)

        return temp1 + temp2