計算最小步數以獲得給定的所需數組


難度級別
經常問 第一資本 思傑 Coursera 新思 合子
排列 數學

問題陳述

假設您有一個僅包含整數0作為其所有元素的數組。 考慮,給你一個長度數組 n 具有所有0,我們必須將0轉換為給定的所需數組。 我們可以將所需的數組命名為 requiredArr 大批。 因此,我們需要計算最小步數以獲得給定的所需數組。 那就是找出將零數組更改為給定所需數組所需的最少操作數。 我們只能執行以下操作。

  1. 加倍運算:我們可以將數組的元素值加倍,或者
  2. 增量操作:我們可以將數組值的元素增加1。

 

desiredArr[] = {1, 2}
3

說明:

將{0,0}轉換為所需的 排列

  • 將兩個元素的值都增加1→(2個操作)
  • 將第二個元素增加1→(再進行1個操作)
  • 總共進行了3次操作。

 

desiredArr[] = {4, 2}
4

說明:

  • 將兩個元素的值都增加1→(2個操作)
  • 將所有數組元素的值加倍→(1個操作)
  • 將第一個元素加倍→(再執行1個操作)
  • 總共進行了4次操作。

 

計算最小步數以獲得給定所需數組的算法

1. Get the desiredArr array.
2. Set output as 0.
3. Check if all the elements given are even, then divide all the elements by 2 and increase the output by 1.
4. Get all of the odd elements, make them even by decrease their value by 1.
5. For every decrement, increase the value of output by 1.
6. We get all zeros in desiredArr array, after completing all the steps.
7. Return output.

 

解釋

我們已經給出了輸入數組,並且還假設我們只包含僅包含元素0的數組,我們要在該數組上執行一個操作以計算最小步數以獲得給定的所需數組。 執行的操作應滿足給定的說明。 這意味著我們僅在執行滿足給定指令的操作時創建所需的數組。

第一個操作是我們可以將數組的元素值增加1。這在n個操作中計數,這意味著如果我們將n個元素的值增加1。第二個操作是將整個數組(而不是元素)加倍,而是將整個數組乘以2。因此,如果將整個數組乘以2,我們可以得到1的運算。 因此,如果我們計算將兩個值都加1的操作數,然後將數組加倍一次,則這意味著我們的操作總數為3。

我們可以將示例作為arr [] = {4,2},並且還需要假設我們有一個0的數組。 因此,首先我們必須將元素的值增加1,因此我們計算2次操作。 現在我們有了{1,1}作為數組。 現在我們將整個數組加倍,因此總共得到{2,2}和3個操作。 我們只需要在第一個位置有4個即可。 因此,我們將該值加倍,到目前為止,我們總共進行了4次操作。 4是獲得所需陣列的最小步數。

這只是一種直觀的理解方式。 但是,除了執行此操作外,我們將輸入數組轉換為0s數組。 因此,為此,我們執行的操作與給定操作相反。 如果元素是奇數,則我們遞減,一旦數組的所有元素都為偶數,就遞減。 我們將每個元素(數組中的元素)除以2,並將其計為單個操作。 例如,[4,2]-> [2,1]-> [2,0]-> [1,0]-> [0,0]會通過顯示的更改。

備註

該技術也用於其他問題。 使用類似的指令將整數A轉換為B就是其中之一。 我們可以將A減1或將A乘2。再一次,我們嘗試將B轉換為A,與提出的問題的其他解決方案相比,這要容易得多。

 

計算最小步數以獲得給定的所需數組

代碼以最少的步數獲得給定的所需數組

C ++代碼

#include<iostream>
using namespace std;

int getMinimumOperations(unsigned int desiredArr[], int n)
{
    int output = 0;
    while (1)
    {
        int zeroArrCnt= 0;

        int i;
        for (i=0; i<n; i++)
        {
            if (desiredArr[i] & 1)
                break;

            else if (desiredArr[i] == 0)
                zeroArrCnt++;
        }
        if (zeroArrCnt== n)
            return output;
        if (i == n)
        {
            for (int j=0; j<n; j++)
                desiredArr[j] = desiredArr[j]/2;
            output++;
        }
        for (int j=i; j<n; j++)
        {
            if (desiredArr[j] & 1)
            {
                desiredArr[j]--;
                output++;
            }
        }
    }
}
int main()
{
    unsigned int arr[] = {4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<getMinimumOperations(arr, n);
    return 0;
}
4

Java代碼

class minimumSteps
{
    public static int getMinimumOperations(int arr[],int n)
    {
        int output = 0;
        while (true)
        {

            int zeroArrCnt= 0;

            int i;
            for (i=0; i<n; i++)
            {
                if (arr[i] % 2 == 1)
                    break;
                else if (arr[i] == 0)
                    zeroArrCnt++;
            }
            if (zeroArrCnt== n)
                return output;

            if (i == n)
            {
                for (int j=0; j<n; j++)
                    arr[j] = arr[j]/2;
                output++;
            }
            for (int j=i; j<n; j++)
            {
                if (arr[j] %2 == 1)
                {
                    arr[j]--;
                    output++;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {4, 2} ;
        System.out.println(getMinimumOperations(arr,arr.length));
    }
}
4

複雜度分析

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。