将所有元素都为零的给定数组转换成目标数组

Question

将所有元素都为零的给定数组转换成目标数组

4

最近我遇到了一个面试问题，我尝试着解决了它，但是面试官希望得到更好的解决方案。这个问题是：

给定一个包含零的源数组和一个包含数字的目标数组，返回你可以从源数组获得目标数组的最小步数。你只允许进行以下操作：在一个操作中，你可以将索引L到R之间的源数组元素的值每个增加1。

我的想法：

Let array be [4,2,3,5] 
cnt=0;
For each sub-array with only non-zero element, subtract minimum of that sub-array from each of the element of that sub-array. Count increases by sum of mins in each subarray
So array becomes :
After first step : [2,0,1,3] cnt+=1*2 (because only one subarray)
After second step : [0,0,0,2] cnt+=2+1 (because two subarray, each requiring an increment operation)
After second step : [0,0,0,0] cnt+=2

有人能帮忙找到更好的算法吗？我也在考虑是否可以使用线段树/二进制索引树，但是无法想出解决方案。

- danish sodhi

4个回答

3

不要将零数组递增并转换为给定数组，而是采用另一种方式 - 尝试通过递减将给定数组变成零数组。

在给定的数组上构建一个线段树。线段树应该能够回答以下查询 - min(left, right) - 在范围left和right之间的最小项的索引。
从range(0，n-1)开始，其中n是数组的大小。在任何时刻，对于query(left，right)，假设最小元素是x，索引是indx。
现在这里有个诀窍。不要实际递减范围left到right之间的元素，因为那样很困难。递归调用range(left，indx-1)和range(indx+1，right)。对于左部分和右部分，您已经知道，您已经从每个元素中递减了dx。所以现在对于任何元素X，您必须像X-dx一样处理。

希望您能理解。我将提供此的C ++实现。

EDIT

请查看代码并使用笔和纸。您会理解这个想法，希望如此。我已经在棘手的部分添加了注释。

class Solution {
public:
    vector<int> segmentTree;
    vector<int> arr;
    int n;
    void init() {
        segmentTree.clear();
        const int SIZE  = pow(2, ceil(log((double) n) / log(2.0)) + 1) - 1;
        segmentTree.resize(SIZE, 0);
        build(1, 0, n - 1);
    }

    // O(n)
    int build(int node, int left, int right) {
        if(left == right) {
            return segmentTree[node] = left;
        }
        int leftNode = node << 1;
        int rightNode = leftNode | 1;
        int mid = left + (right - left) / 2;
        int leftIdx = build(leftNode, left, mid);
        int rightIdx = build(rightNode, mid + 1, right);
        return segmentTree[node] = (arr[leftIdx] <= arr[rightIdx]) ? leftIdx : rightIdx;
    }

    int query(int node, int left, int right, int x, int y) {
        if(x > right or y < left) return -1;
        if(left >= x and right <= y) return segmentTree[node];
        int leftNode = node << 1;
        int rightNode = leftNode | 1;
        int mid = left + (right - left) / 2;
        int leftIdx = query(leftNode, left, mid, x, y);
        int rightIdx = query(rightNode, mid + 1, right, x, y);
        if(leftIdx == -1) return rightIdx;
        if(rightIdx == -1) return leftIdx;
        return (arr[leftIdx] <= arr[rightIdx]) ? leftIdx : rightIdx;
    }

    int query(int x, int y) {
        return query(1, 0, n - 1, x, y);
    }

    int convertUtil(int left, int right, int dx) {
        if(left > right) return 0;
        int mid = query(left, right);
        int minElement = arr[mid];

        int cnt = 0; // the number of operation

        // dx is the amount that has been already decremented from this range
        // So you have to treat every element X as (X - dx)
        cnt += (minElement - dx);

        cnt += convertUtil(left, mid - 1, minElement) + convertUtil(mid + 1, right, minElement);

        return cnt;
    }

    int convert(vector<int>& arr) {
        this->arr = arr;
        this->n = arr.size();
        init();
        return convertUtil(0, n - 1, 0);
    }
};

// vector<int> arr {4,2,3,5};
// cout << Solution().convert(arr); // OUTPUT: 7

- Kaidul

请问您能否分享一下如何高效地完成更新函数。我的意思是，将每个元素减一会导致线段树发生变化（所有元素），我认为这将是一个代价高昂的操作。 - danish sodhi

@crystal，请检查我刚刚添加的代码。实际上，您不需要update方法，因为这会使其变得昂贵。请检查代码，如果您需要任何解释，请告诉我。我也将更新我的答案。 - Kaidul

非常感谢您提供如此详细的解释:D - danish sodhi

1

使用栈。运行时间为O(moves + length)。

每次值增加1时，将(position, end_val)添加到栈中。每次值减少1时，移除栈顶元素并将其位置与当前位置左侧的位置配对。

例如，[5, 3, 2, 5]

process 5: an increase. Stack is now (0,1), (0,2), (0,3), (0,4), (0,5)
process 3: a decrease at index 1. Remove the top two elements from the stack and record these moves (0,0) (0,0). The stack is now (0,1), (0,2), (0,3)
process 2: a decrease at index 2. Remove the top element from the stack and record (0,1). The stack is now (0,1), (0,2)
process 5: an increase at index 3. The stack is now (0,1), (0,2), (3,3), (3,4), (3,5)
process 0 (implied): a decrease at index 4. record (3,3), (3,3), (3,3), (0,3), (0,3)

最终步骤：(0,0) (0,0), (0,1), (3,3), (3,3), (3,3), (0,3), (0,3)。

您可以通过单独记录多级位置更改（例如第一步为(0,5)）来节省空间，但时间效率相同，因为每个步骤只能将值更改1。

- Dave

0

public int minNumberOperations(int[] target) {
    int ans = target[0];
    for(int i=1; i < target.length; i++){
        if(target[i]>target[i-1]){
            ans += target[i]-target[i-1];
        }
    }
    return ans;
 }

- bucky roberts

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mhelvens · Accepted Answer

这个问题有一个简单的 O(n) 运行时，O(1) 内存的解决方案。

可以将 target 数组看作一个给定高度的山脉范围。最小操作次数是您需要放置的非断开的高度为 1 的山脉层数。

但更容易的想法是，如果你从任何方向穿越这个山脉范围，总共需要攀登的距离。

这里是一个 C++ 实现。

int minNumberOperations(const vector<int>& target) {
  int result = 0, prev = 0;
  for (int height : target) {
    result += max(0, height - prev);
    prev = height;
  }
  return result;
}