通过右移数组元素将数组转换为二进制数组

原文:https://www . geeksforgeeks . org/通过右移数组元素将数组转换为二进制数组/

给定一个由 N 个整数组成的数组arr【】，任务是对数组元素执行个右移位操作，将给定数组转换成个双音素数组。

示例:

输入: arr[] = {7，3，4，5，3} 输出: 56 96 128 80 48 解释: 对数组元素执行如下操作:

  • 7 → 00000111 → 3 次右移→ 00111000 → 56
  • 3 → 00000011 → 5 次右移→ 01100000 → 96
  • 4 → 00000100 → 5 次右移→ 10000000 → 128
  • 5 → 00000101 → 4 右移→ 01010000 → 80
  • 3 → 00000011 → 4 右移→ 00110000 → 48

经过上述操作后，修改后的数组是{56，96，128，80，48}，这是 Bitonic 数组。

输入: arr[] = {255，243，23，141，46} 输出: -1

方法:按照给定的步骤解决问题

下面是上述方法的实现:

Python 3

# Python program for the above approach

# Function to check if an
# array arr[] is Bitonic or not
def isPeak(arr):

    # Traverse the first half of arr[]
    for i in range(len(arr)//2, len(arr)-1):
        if arr[i] < arr[i + 1]:
            return False

    # Traverse the second half of arr[]
    for i in range(len(arr)//2):
        if arr[i] > arr[i + 1]:
            return False

    # Return true if arr[] is bitonic
    return True

# Function to maximize the value of N
# by performing right shift operations
def maximize(n):

    Ele = n
    ans = n

    for idx in range(7):

        # Right shift by 1
        if Ele & 1:
            Ele >>= 1
            Ele += 2**32
        else:
            Ele >>= 1

        # Update the value of ans
        ans = max(ans, Ele)

    return ans

# Function to arrange array in descending
# order by right shift operations
def makeDec(arr):

    # Maximise the array arr[0]
    prev = maximize(arr[0])
    arr[0] = prev

    # Iterate through array arr[]
    for i in range(1, len(arr)):

        optEle = arr[i]

        # Flag to find the first
        # element less than prev
        flag = True

        # Update Ele as arr[i]
        Ele = arr[i]

        for idx in range(7):

            # Right shift by 1
            if Ele & 1:
                Ele >>= 1
                Ele += 2**32
            else:
                Ele >>= 1

            if Ele < prev and flag:

                  # Update the optEle
                optEle = Ele

                # Unset the flag
                flag = False

            if Ele < prev:

                  # Update the optEle
                optEle = max(optEle, Ele)

          # Update the array arr[i]
        arr[i] = optEle

        # Update the value of prev
        prev = arr[i]

    # Return the array
    return arr

# Function to find the peak
# element of the array arr[]
def makePeak(arr):

    # First half of the array
    first = arr[:len(arr)//2 + 1]
    first.reverse()

    # Second half of the array
    second = arr[len(arr)//2:]

    # Merg both halves
    ans = makeDec(first)[::-1] + makeDec(second)[1:]

    # Function Call
    if isPeak(ans):
        return ans

    return -1

# Driver Code

# Given array
arr = [7, 3, 4, 5, 3]

# Function Call
print(makePeak(arr))

Output:

[1879048192, 3221225472, 4294967296, 2684354560, 1610612736]

时间复杂度: O(N * log(M))，其中 M 为arr 的最大元素[] 。 辅助空间: O(1)

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/32626.html