logo标签列表

使数组严格递增所需的最小更改次数

algorithmdynamic-programming
7
我有一个问题，我们有一个正数数组，我们需要通过对数组元素进行零次或多次更改来使其严格增加。我们被要求找出使数组严格增加所需的最小更改次数。 示例 如果数组为1 2 9 10 3 15，则答案为1，如果将3更改为介于12到14之间的某个数字。
如果1 2 2 2 3 4 5，则答案为5，因为需要将2更改为3，然后将2更改为4，将3更改为5，将4更改为6，将5更改为7。 约束条件： 数组中的元素数量<= 10^6
每个元素<= 10^9
请问有人能给我一个算法吗？
详细问题及样本测试用例链接 https://www.hackerearth.com/problem/algorithm/find-path/

由于这是一个极小/极大化问题，听起来像动态规划，但我不确定。

无论是否有作业，你都应该尝试解决问题。所给的限制条件让它听起来很像编程竞赛。 - Bernhard Barker
1
我认为这里也有一些关于非负/正数的限制，否则对于第二个例子，你可以将1改为-1，(1st) 2改为0，(2nd) 2改为1。 - Bernhard Barker
1
不需要动态内容! - Kaustav Ray
你是否需要实际确定所需更改，还是仅需要确定需要进行的更改数量？如果是后者，我认为可以扫描列表一次并注意当前有多少元素不符合条件，再稍微跟踪一下间隔，以便注意到更改一个元素会破坏尚未破坏的相邻元素的情况。 - twalberg
6个回答
13

提示1

这与标准的最长上升子序列问题非常接近，可以在O(nlogn)内解决。

如果您可以将数字更改为小数，则答案将是相同的。 (最小更改次数=字符串长度-最长递增子序列的长度)

但是，由于您需要介于不同整数值之间，因此必须稍微修改标准算法。

提示2

考虑一下如果通过x[i]=x[i]-i来更改数组会发生什么。

现在，您需要通过进行最小数量的更改来修改此更改后的数组，使每个元素增加或保持不变。

现在，您可以在该数组中搜索最长的非递减子序列，并且这将告诉您可以保持多少个元素不变。

但是，这可能仍然使用负整数。

提示3

将算法修改为仅使用正数的一种简单方法是在数组开头添加许多数字。

例如，将1、2、9、10、3、15更改为-5、-4、-3、-2、-1、1、2、9、10、3、15

然后，您可以确信最优答案永远不会决定使1变为负数，因为这将花费太多时间使所有负数更小。

（您还可以修改最长递增子序列算法以具有附加约束条件，但在面试情况下正确编写可能更难。）

例1

按照初始示例进行操作：

原始序列

1,2,9,10,3,15

在开头添加虚拟元素

-5,-4,-3,-2,-1,1,2,9,10,3,15

从数组中减去位置

-5,-5,-5,-5,-5,-4,-4,2,2,-6,5

找到最长的非递减序列

-5,-5,-5,-5,-5,-4,-4,2,2,*,5

所以答案是改变一个数字。

例子2

原始序列

1,2,2,2,3,4,5

在开头添加虚拟元素

-5,-4,-3,-2,-1,1,2,2,2,3,4,5

从数组中减去位置

-5,-5,-5,-5,-5,-4,-4,-5,-6,-6,-6,-6

找到最长的非递减序列

-5,-5,-5,-5,-5,-4,-4,*,*,*,*,*

所以答案是改变5个数字。

我们能否在不添加虚拟节点的情况下实现呢？其次，如果最后一个节点是10^9，那么我们必须添加10^9个负虚拟节点，这是不必要的，并且会增加我们的复杂度。而且在C/C++中，我们无法使用那么多的内存。 - user3158205
@PeterdeRivaz你是错的，你的方法在例子50,51,50,50,52,53,57中是不起作用的，因为你的方法总是会改变数字的下一个位置，而且永远不会回退，因为你在开头加了一个递增的数组。 - Eugen Halca
1
你只需要添加10^6个虚拟节点（与序列长度相同，而不是最大数量）。你也可以不添加虚拟节点，但这需要对标准查找最长递增子序列算法进行轻微修改。 - Peter de Rivaz
@EugenHalca 我建议的方法可以减少数字，但不能减少到小于0。找出最长非递减子序列是选择未改变的数字。改变后的数字可以增加或减少。 - Peter de Rivaz
0

将 最长递增子序列 的修改以适应在两个连续递增元素之间挤压整数值，可以确保我们在适当的位置具有整数值。

修改后的 LIS 代码：

int convert(vector<int> v){
vector<int> lis(v.size(), 1);  
for(int i = 1; i < v.size(); i++){   
    for(int j = 0; j < i; j++){  
        if(v[i] > v[j] && lis[i] < lis[j]+1 && (i-j) <= (v[i]-v[j]))   
            lis[i] = lis[j]+1;  
    }  
}  
int max_lis = 0;  
for(int i = 0; i < v.size(); i++)  
    max_lis = max(max_lis, lis[i]);  
int ans = v.size() - max_lis;
return ans;
}
0

O(nlogn) 运行时间

import java.util.ArrayList;
    import java.util.Scanner;

    public class Modify_The_Sequence {
        private static int n;
        private static int[] a;
        private static ArrayList<Integer> b;
        private static ArrayList<Integer> c;

        public static void main(String args[]) {
            Scanner d = new Scanner(System.in);

            n = d.nextInt();

            b = new ArrayList<>();
            c = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int x = d.nextInt();
                if (x - (i + 1) >= 0) {
                    b.add(x - (i + 1));
                }

            }

            /*
             * b.clear(); b.add(1); b.add(7); b.add(10); b.add(2); b.add(3);
             */
            // System.out.println(b);
            c.add(b.get(0));
            solve();
            System.out.println(n - c.size());
            // System.out.println(c);
        }

        private static void solve() {
            // TODO Auto-generated method stub
            for (int i = 1; i < b.size(); i++) {
                binaerysearch(0, c.size() - 1, i);
            }
        }

        private static void binaerysearch(int i, int j, int k) {
            // TODO Auto-generated method stub
            int p = (i + j) / 2;
            if (i == j) {

                if (c.get(i) <= b.get(k)) {
                    if (i == c.size() - 1)
                        c.add(b.get(k));
                    else {

                        c.add(i + 1, b.get(k));
                        c.remove(i + 2);
                    }
                } else if (c.get(i) > b.get(k)) {
                    c.add(i, b.get(k));
                    c.remove(i + 1);

                }

            } else {
                if (c.get(p) > b.get(k)) {
                    if (p - 1 > i)
                        binaerysearch(i, p - 1, k);
                    else
                        binaerysearch(i, i, k);
                } else if (c.get(p) <= b.get(k)) {
                    if (p + 1 < j)
                        binaerysearch(p + 1, j, k);
                    else
                        binaerysearch(j, j, k);
                }
            }
        }
    }
0

受到@Peter de Rivaz的启发，

我发现这个问题的关键条件是：num[i]-i >= num[j]-j >= 0 (i > j)。

以下Java代码（O(NlgN)）是标准最长上升子序列算法的轻微修改，我们在此跳过所有num[i]，其中num[i]-i < 0。

  static int resolve(int... nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int right = 0;
    for (int i = 1; i < nums.length; i++) {
      if (nums[i] >= i) {
        int realNum = nums[i] - i;
        if (realNum >= dp[right]) {
          right++;
          dp[right] = realNum;
        } else {
          dp[binarySearch(dp, 0, right, realNum)] = realNum;
        }
      }
    }
    return nums.length - (right + 1);
  }

  static int binarySearch(int[] nums, int left, int right, int key) {
    while (left <= right) {
      int mid = (left + right) >>> 1;
      if (nums[mid] > key) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
-1

O(n) 运行时间：

def min_changes(li):
  change, check = 0, 0
  li_len = len(li)
  if li_len in [0,1]:
    return change
  else:
    check = li[0]
  for i in range(1, len(li)):
    if check >= li[i]:
      li[i] = check +1
      change += 1
      check += 1
    else:
      check = li[i]
  return change
4
虽然这段代码片段可能解决了问题，但是加上解释说明真的有助于提高帖子质量。请记住，您正在为未来的读者回答问题，而这些人可能不知道您建议使用代码的原因。同时，请尽量避免在代码中添加过多的解释性注释，这会降低代码和解释的可读性！ - kayess
在尝试回答更多问题之前，请阅读如何撰写一个好的答案？。 - user177800
-1

使用Python实现时间复杂度为O(n)、空间复杂度为O(1)的解决方案

arr = [1,2,2,2,3,4,5]
count = 0
for i in range(len(arr)-1):
    if(arr[i]>=arr[i+1]):
        arr[i+1] = arr[i]+1
        count += 1
print(count)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接