贪心算法买车

发表于 分类于
学习笔记

翻译

greedy algoritm: 贪心算法
budget: 预算

条件

1
2
3
budget:100
prices: [20,40,30,90,50]
sort: [20,30,40,50,90]

算法

1
2
3
4
5
6
7
8
9
10
11
12
public int buyCars(int budget, int[] prices) {
    Arrays.sort(prices);
    int ans = 0;
    for (int car : prices) {
        if (budget >= car) {
            ans++;
            budget -= car;
        } else
            break;
    }
    return ans;
}

时间复杂度: 时间复杂度: O(N*logN)===>O(N*logN)+O(N)
O(n²+N*logN)=O(n²)
O(N³+n²)=O(n³)