优化hackerrank算法

Question

优化hackerrank算法

6

在HackerRank上有人问了我这个问题，但我还没有找到一种不会超时的解决方案。我使用了PHP语言，规定时间为9秒...

这个问题的思路是，“售票摊位”上有一定数量的门票，比如9张。它们所卖出的每一张票的价格都是剩余门票的数量，因此第一张票的价格为$9，第二张为$8，以此类推...

你会得到两行数据，例如：

2 4
1 5

第一行包含两个数字：stall的数量和售出的票数。

第二行包含最初每个stall的票数列表，因此在这种情况下，stall 1有1张票，stall 2有5张票。

问题是：售出给定数量的门票可以获得的最大收益是多少？

在本例中，您从stall 2出售4张门票，价格为5 + 4 + 3 + 2 = $14。

那么如何解决它呢？我想出了两种方法，但都没有时间完成：

1.将stall编号（第二行）加载到数组中。通过该数组N次（售出的门票数）进行筛选，选择最大的元素，并将其添加到累加器中，将该数字减少。然后您会在汇聚器中得到总数。

2.将stall编号加载到一个数组中。对数组进行排序。倒序遍历该数组并执行以下操作：存储该数字（当前值），将其添加到累加器中，转到下一个值。如果它与之前的值（当前值）相同，则将其添加到累加器中，将其减去1，并继续执行。如果它不同，请返回数组末尾并重新开始。重复此过程N次（内部循环，而不是外部循环）。

问题：两者都无法解决。

有人能想出更好的解决方案吗？

- Daniel K

这个问题每个摊位的最大票数是多少？ - RBarryYoung

你知道吗，我记不清是否有最大值，但最大的总票数和摊位数量是10万。 - Daniel K

5个回答

2

如果您害怕DP，那么这是您应该尝试的O(n)解决方案。以下代码仅考虑最大元素，并继续将其减小，直到达到所需的票数。它通过将乘法因子存储为哈希映射中的值来跟踪乘法因子。最后，如果票数大于所需票数，则从结果中减去最近添加的票价，直到票数等于所需票数。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TicketClass {
    public static void main(String[] args){
        int[] arr = {10,10,2,8,6,4};
        int ticket = 23;
        Arrays.sort(arr);
        int mul = 1;
        int k = 0;
        System.out.print("Hello World");
        long res = 0;
        Map<Integer,Integer> hm = new HashMap<>();
        for(int i:arr){
            if(hm.containsKey(i)){
                hm.put(i,hm.get(i)+1);
            }
            else
                hm.put(i,1);
        }

        int curr = arr[arr.length-1];

        while(k < ticket){
            mul=hm.getOrDefault(curr,mul);
            res += curr*mul;
            curr--;
            k += mul;
            if(hm.containsKey(curr))
                hm.put(curr,hm.get(curr)+mul);
        }

//End of while loop
        curr++;
        while(k > ticket){
            k--;
            res -=curr;
        }
        System.out.println("ticket "+k);
        System.out.println(res);
    }
}

- Neha Gupta

0

最大堆解法的优化：

你不需要逐个移除票。如果你有一个顶部的窗口，你需要知道它有多少张票和下一个窗口有多少张票。然后你就可以一次性去掉差额并计算出总价格。
通过轻微的修改，如果你有多个具有相同最大票数的窗口，你也可以做到同样的事情。

- GorvGoyl

0

让我们看看为什么您的解决方案超时。

将摊位号码（第二行）加载到数组中。遍历该数组N次（出售门票的数量），选择最大的数字，将其添加到聚合器中，减少该数字。然后您就可以在聚合器中得到总数。

这是O（N * M）的时间复杂度，其中N是要出售的门票数量，M是售票亭的数量。这基本上是一种暴力方法，通常不足以击败hackerrank的测试。

将摊位号码加载到数组中。对数组进行排序。向后遍历数组，并执行以下操作：存储该数字（当前值），将其添加到聚合器中，转到下一个值。如果它与当前值相同，则将其添加到聚合器中，从中减去1，继续前进。如果它不同，则返回到数组末尾并重新开始。重复进行N次（内部循环，而不是外部循环）。

也许是我自己的问题，但我并不真正理解你在这里的意思。从我看到的来看，它听起来仍然是O(N*M)。如果有大量门票被多次减少以至于打破了之前制作的排序，你该如何处理？

你需要的是一种数据结构，可以高效地检索当前最大值，并且可以高效地弹出/插入新元素。看起来最大堆是一个很好的选择。只需将每个售票亭中可用门票数量保留在最大堆中。要使用M个售票亭出售N张门票，请执行以下操作：

提取最大值 - O(log(M))
将其添加到结果累加器中 - O(1)
递减它 - O(1)
将其插入堆中 - O(log(M))

总体复杂度为O(N*log(M))，这可能是您能做到的最好的。

C++实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int max_revenue(vector<int> &tickets, int n) {

    make_heap(tickets.begin(), tickets.end());

    int res = 0;
    for (int i = 0; i < n; i++) {
        res += tickets.front();
        pop_heap(tickets.begin(), tickets.end());
        tickets[tickets.size()-1]--;
        push_heap(tickets.begin(), tickets.end());
    }

    return res;
}

int main(void) {
    int booths;
    cin >> booths;
    int n;
    cin >> n;

    vector<int> tickets(booths);
    for (int i = 0; i < booths; i++)
        cin >> tickets[i];

    cout << max_revenue(tickets, n) << endl;

    return 0;
}

- Filipe Gonçalves

我之前从未听说过max_heap。我的第二个解决方案假设你有一个排序好的数组，只需向后遍历数组，直到值发生变化，然后再重新开始。所以，假设你有1,1,2,4,5,6,7,8,8...它会这样做：1）添加8并将其减少到7，向左移动。2）添加8并将其减少到7，向左移动。3）这不是8，所以回到末尾。现在数组变成了1,1,2,4,5,6,7,7,7，聚合器为16，所以1）添加7，减少，向左移动2）添加7，减少，向左移动等等。初始排序不比M * log M更好，然后+ N进行下一步操作... - Daniel K

0

这里是 PHP 的一个实现，与其他一些答案不同，它不会创建额外的数组。解决此问题有很多不同的方法，请查看并可能在将来给您带来想法。有很多方法可以改进它以实际使用，但这只是展示快速解决问题的替代方法。

class booth {

public $booths = [];
public $left = 0;
public $count = 0;
public $total = 0;
public $booth = 0;
public $nextBooth = 0;

function __construct() {
    $this->booths = [3, 7, 5, 2, 0, 2, 5, 15, 9, 1, 39, 91, 0, 58, 29];
    $this->left = 25;

    sort($this->booths);

    $this->booth = array_pop($this->booths);


    while($this->left > 0 && count($this->booths) > 0) {
        $this->count++;
        $this->nextBooth = array_pop($this->booths);        
        $this->countTotal($this->booth - $this->nextBooth);
    }

    // found end of array -- clear out any that are left
    if($this->left > 0)
        $this->countTotal(1);

    echo "total: " + $this->total."\r\n";
}

// everything global except loops
function countTotal($loops) {

    for($i = 0; $i < $loops, $this->left > 0; $i++) {
        if ($this->count > $this->left) 
            $this->count = $this->left;

        $this->total += $this->booth * $this->count;
        $this->left -= $this->count;
        $this->booth--;

    }
}

}

new booth();

- Jason G

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

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

- RBarryYoung · Accepted Answer

创建一个数组，记录剩余票数的摊位数量（例如 {0, 3, 0, 2} 表示有 2 个摊位有 3 张票，3 个摊位有 1 张票）。
将最高非零项减一，将下面的项加一，并将该项的索引添加到总数中。
每售出一张票就重复步骤 #2 一次。

还有一种明显的改进方法是通过“最高摊位中的票数”和“剩余待售票数”中的最小值相乘来计算。

注意：为了使这个算法性能良好，你所使用的编程语言必须支持真正的数组（即无论索引是多少，访问时间都是恒定的）。我不了解 PHP，但有些语言（比如 JS？）使用顺序列表来模拟数组，但它们的性能并不相同。

以下是 Java 实现该方法的代码（请阅读注释以更好地理解）：

        int[] stalls = new int[] { 4, 7, 1, 4, 8, 8 };
        int t = 4;

        Arrays.sort(stalls);

        int tickets = stalls[stalls.length - 1];
        int[] dp = new int[tickets + 1];

        for (int i = 0; i < stalls.length; i++) {
            dp[stalls[i]]++;
        }

        int total = 0;
        int i = dp.length - 1;

        while (t > 0) {
            if (dp[i] > 0) {
                total += i;
                t--;
                dp[i]--;
                dp[i - 1]++;
            } else {
                i--;
            }
        }

        System.out.println(total);