Конвертировать данный массив со всеми нулями в целевой массив - PullRequest
Новая
       42

Конвертировать данный массив со всеми нулями в целевой массив

0 голосов
/ 21 мая 2018

Недавно я наткнулся на вопрос об интервью.Я пытался решить это, но интервьюер искал лучшее решение.Вопрос в следующем:

Учитывая исходный массив, содержащий нули, и целевой массив, содержащий числа, вернуть наименьшее количество шагов, в которых вы можете получить цель из источника.Вам разрешено выполнять только следующую операцию: Вы можете увеличить значения элементов исходного массива каждый на 1 от индекса L до индекса R. за одну операцию.

Мои мысли: 

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

Может ли кто-нибудь помочь найти лучший алгоритм?Я также думаю, можно ли использовать дерево сегментов / дерево двоичных индексов, но не смогу найти решение.

Ответы [ 2 ]

0 голосов
/ 21 мая 2018

Используйте стек.Время выполнения O (ходы + длина).

Каждый раз, когда значение увеличивается на 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.

0 голосов
/ 21 мая 2018

Вместо того, чтобы увеличивать нулевой массив и преобразовывать его в данный массив, атакуйте другим способом - попробуйте превратить данный массив в нулевой массив, уменьшив его.

  • Постройте дерево сегментов сверхуданного массива.Дерево сегментов должно отвечать на эти запросы - 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
...