java - find minimum cost to get unique items - Stack Overflow

admin管理员组

文章数量:1291135

Here is the task:

Given an array of numbers called nums of size n and another array called cost of size n

cost[i] where i is index represents the cost to increment an element nums[i]

Calculate the minimum cost to make all items in nums distinct.

Example:

nums = [3,7,9,7,8]
cost = [5,2,5,7,5]

answer = 6

Explanation:

In nums element 7 is repeated twice with cost as [2,7]

we can pick the number 7 with cost 2, and increment it 3 times so it changes to 7 -> 8 -> 9 -> 10. so incremented 3 times, so cost is 2 * 3 = 6

Calculate the minimum cost to make the nums array distinct

constraints :

1 <= n <= 10^5
1 <= nums[i] <= 10^9
1 <= cost[i] <= 10^4

My approach to solve this was to pick initial unique items and store in a HashSet in Java

Next get the duplicate items in nums in sorted order, and calculate the least cost for each element, then increment item till it becomes unique and calculate cost for that element.

Similarly get the sum of costs to increment all duplicates till the become unique in nums

But my approach is not correct because it is not always true that we can process from smallest to largest item and get the answer

I am looking for the correct approach to solve this problem in less time complexity.

Here is the task:

Given an array of numbers called nums of size n and another array called cost of size n

cost[i] where i is index represents the cost to increment an element nums[i]

Calculate the minimum cost to make all items in nums distinct.

Example:

nums = [3,7,9,7,8]
cost = [5,2,5,7,5]

answer = 6

Explanation:

In nums element 7 is repeated twice with cost as [2,7]

we can pick the number 7 with cost 2, and increment it 3 times so it changes to 7 -> 8 -> 9 -> 10. so incremented 3 times, so cost is 2 * 3 = 6

Calculate the minimum cost to make the nums array distinct

constraints :

1 <= n <= 10^5
1 <= nums[i] <= 10^9
1 <= cost[i] <= 10^4

My approach to solve this was to pick initial unique items and store in a HashSet in Java

Next get the duplicate items in nums in sorted order, and calculate the least cost for each element, then increment item till it becomes unique and calculate cost for that element.

Similarly get the sum of costs to increment all duplicates till the become unique in nums

But my approach is not correct because it is not always true that we can process from smallest to largest item and get the answer

I am looking for the correct approach to solve this problem in less time complexity.

• java
• algorithm

Share Improve this question Follow edited Feb 16 at 7:12 CodeCrusader asked Feb 13 at 20:18 CodeCrusaderCodeCrusader 43111 silver badge1111 bronze badges 9

• your constraints are wrong. The number of elements in nums[] must be the same as the number of elements in cost[] – ravenspoint Commented Feb 13 at 20:27
• @ravenspoint - re-read constraints. They are on individual values of list items and not for the size of lists. – PM 77-1 Commented Feb 13 at 20:29
• 1 Looks like a good candidate for backtracking. – PM 77-1 Commented Feb 13 at 20:30
• @PM77-1 How do you interpret "cost[i] where i is index represents the cost to increment an element nums[i]"? – ravenspoint Commented Feb 13 at 20:36
• 4 If this problem comes from a web page, it would be polite, and possibly helpful to include a link to that page. – Old Dog Programmer Commented Feb 13 at 21:05

 |  Show 4 more comments

4 Answers 4

Sorted by: Reset to default 4

Create a list of pairs of [n, cost] and sort it by n ascending, cost descending. Create an empty priority queue ordered by cost descending. Then do it like this pseudocode:

last_n = -1
i = 0
total_cost = 0
while queue is not empty or i < pairs.length:
    if queue is empty:
        if pairs[i][0] == last_n:
            // Add to the queue
            queue.add(pairs[i])
            i++
        else:
            // use pairs[i]
            last_n = pairs[i][0]
            i++
    else if pairs.length <= i or last_n+1 < pairs[i][0]:
        // pull from the queue
        last_n++
        pair = queue.pop()
        total_cost += (last_n - pair[0]) * pair[1]
    else if pairs[i][0] <= last_n or pairs[i][1] < queue.peek()[1]:
        // add this pair to the queue
        queue.add(pairs[i])
        i++
    else:
        // pairs[i] has to be last_n+1 and costs more than the queue.
        // so just record emitting it unincremented.
        last_n = pairs[i][0]
        i++

Assuming no logic errors on my part, this should always succeed in finding the answer in time O(n log(n)). Because each pair is either used once, or else is added to the queue, then removed at the right position and its contribution to the total cost calculated. And the queue operations are O(log(n)).

Another O(n log n) solution:

Go through the numbers in increasing order. Use a max-heap of costs of not yet finalized numbers. Implicitly increase the numbers as you go, so all numbers reflected by the heap have the same value heapnum. And heapsum is the sum of all costs on the heap, for efficiency.

(Note I renamed cost to costs so we can use cost for a single cost.)

nums  = [3,7,9,7,8]
costs = [5,2,5,7,5]

# Create max-heap of costs, sum is zero, doesn't reflect a num yet
heap = MaxHeap()
heapsum = 0
heapnum = None
paid = 0

# Go through the nums in sorted order
for num, cost in sorted(pairs(nums, costs)) + [(infinity, infinity)]:

    # Finalize numbers smaller than the current num.
    # Always pick the most expensive and
    # increase all others and pay for that.
    while heap isnt empty and heapnum < num:
        heapsum -= heap.pop()
        heapnum += 1
        paid += heapsum

    # Add the current num to the heap
    heap.push(cost)
    heapsum += cost
    heapnum = num

print(paid)

Below is a Python implementation along with a Python implementation of btilly's. They give the same results for a variety of test cases. For worst cases they take about half a second (mine is faster, but btilly's is a direct naive translation of their pseudo code, could perhaps be optimized). As Python only has min-heap, I negate the costs in it to get max-heap behavior.

from heapq import *

def no_comment():
    heap = []
    heapsum = 0
    paid = 0
    for num, cost in sorted(zip(nums, costs)) + [[1e99] * 2]:
        while heap and heapnum < num:
            heapsum += heappop(heap)
            heapnum += 1
            paid += heapsum
        heappush(heap, -cost)
        heapsum += cost
        heapnum = num
    return paid


def btilly():
    pairs = sorted(zip(nums, costs), key=lambda pair: (pair[0], -pair[1]))

    queue = []
    def queue_add(pair):
        heappush(queue, (-pair[1], pair))
    def queue_pop():
        return heappop(queue)[1]
    def queue_peek():
        return queue[0][1]

    last_n = -1
    i = 0
    total_cost = 0
    while queue or i < len(pairs):
        if not queue:
            if pairs[i][0] == last_n:
                # Add to the queue
                queue_add(pairs[i])
                i += 1
            else:
                # use pairs[i]
                last_n = pairs[i][0]
                i += 1
        elif len(pairs) <= i or last_n+1 < pairs[i][0]:
            # pull from the queue
            last_n += 1
            pair = queue_pop()
            total_cost += (last_n - pair[0]) * pair[1]
        elif pairs[i][0] <= last_n or pairs[i][1] < queue_peek()[1]:
            # add this pair to the queue
            queue_add(pairs[i])
            i += 1
        else:
            # pairs[i] has to be last_n+1 and costs more than the queue.
            # so just record emitting it unincremented.
            last_n = pairs[i][0]
            i += 1
    
    return total_cost


from time import time
import random
from itertools import product

# Example from the question
nums = [3,7,9,7,8]
costs = [5,2,5,7,5]
print(no_comment(), btilly())

# Test case from btilly's comment
nums = [1, 1, 2, 3, 5, 5]
costs = [2, 3, 1, 4, 5, 6]
print(no_comment(), btilly())

# Large random test cases
n = 10**5
for e in range(0, 10):
    nums = random.choices(range(1, 10**e+1), k=n)
    costs = random.choices(range(1, 10**4+1), k=n)

    t0 = time()
    noc = no_comment()
    t1 = time()
    bti = btilly()
    t2 = time()

    print()
    print(noc == bti)
    print(noc, t1 - t0, 'no_comment')
    print(bti, t2 - t1, 'btilly')

# Many small test cases
for n in range(4):
    for nums, costs in product(product(range(1, 9), repeat=n), repeat=2):
        noc = no_comment()
        bti = btilly()
        if noc != bti:
            print(noc, bti, nums, costs)

Attempt This Online!

This is an assignment problem

Naive algorithm:

• Create an array containing the numbers that are missing from nums[] that are in the range min element in nums to max element in nums. Call it holes[]

• Link each number in nums to the numbers that are greater in holes[]

• Assign to each link the cost of getting from the num to the hole

• Use the maxflow algorithm to find the cheapest way to assign each num to a unique hole.

This will give you a feasible solution with reasonable cost.

However, there will be cases where is is not optimal. This occurs when a cheaper result could be obtained by moving a number to leave a hole for a smaller number to fill.

Here's my naive approach, probably not the fastest... but if I don't publish it I won't know about it!!!.

public class Main {

   int nums[] = { 3, 7, 9, 7, 8 },
       costs[] = { 5, 2, 5, 7, 5 };

     // we look for the repeated pair of numbers
   void findRepeats() {
      for( int i = 0; i < nums.length; i ++ ) {
         for( int k = 0; k < nums.length; k ++ ) {
            if( i != k ) {
               if( nums[ i ] == nums[ k ] ) {
                  change( i, k );
                  return;
               }
            }
         }
      }
   }

   void change( int i, int k ) {

        // we take the repeated number
      int aux = nums[ i ];
      while( true ) {

           // if the repeated number plus “1” is not in the array
         if(  ! isHere(  ++ aux ) ) {

              // "aux - nums[ i ]" gives us the number of increments we have made
              // and "min( costs[ i ], costs[ k ] )" gives us the minimum cost of each 
              // operation, it only remains to return the product of both operations
            System.out.println( ( aux - nums[ i ] ) * min( costs[ i ], costs[ k ] ) );
            return;
         }
      }
   }

   boolean isHere( int num ) {
      for( int i = 0; i < nums.length; i ++ ) {
         if( nums[ i ] == num ) {
            return true;
         }
      }
      return false;
   }

   public static void main( String[] args ) {
      new Main().findRepeats();
   }
}

本文标签： javafind minimum cost to get unique itemsStack Overflow