时间戳

首页 > 解决方案 > 计算最大可能对的算法

algorithm - 计算最大可能对的算法

问题描述

我有一组数字说arr=[3,4,2,3,1]。这里的索引arr代表数字，而arr[index]代表该数字的频率。对于arr我们有的例子

1 three times
2 four times
3 two times
4 three times
5 one time

一对可以由两个数字组成，它们的绝对差为 0 或 1。我们需要找到最大可能的对。一个数字的使用频率不能超过其提供的频率。例如arr对可以是：
(1,1),(2,2),(2,2),(3,3),(4,4),(4,5)
因此6是答案。
注意：这里我们剩下一个额外的 1 但这没关系。

我的方法：
计算每个数字的 mod 2 并获得一个由 0 和 1 组成的数组，并且每个频率更新计数为count += arr[i]/2. 因此，对于示例，arr我将留下： [1,0,0,1,1]
现在，如果我看到任何两个连续的 1 更新计数减 1

它适用于示例测试用例，但在隐藏测试用例中失败。谁能帮我弄清楚我的想法有什么问题？

失败案例：
[34,2,435,45,57,6,8,3,57,235]
我的输出：440
预期输出：441

标签： algorithm

解决方案

背后的逻辑是

将 arr[i]/2 带入计数，如果奇数是元素，则将一个作为下一个进位

      public static void main(String args[]) {
                int[] arr=new int[]{34,2,435,45,57,6,8,3,57,235};
                int len=arr.length;
                int count=0,prev=0;
                if(arr[0]%2!=0)prev=1;
                count+=arr[0]/2;
                for(int i=1;i<len;i++){
                    if(prev==1){
                       arr[i]--;
                       count++;
                    }
                    if(arr[i]%2!=0)prev=1;
                    else prev=0;
                    count+=arr[i]/2;
                    
                }
        
              System.out.println(count);
        }

时间复杂度为 O(n)，空间复杂度为 O(1)

推荐阅读