c - 修改数组任意元素

Question

给定一个整数数组，可以任意修改任意多个正整数，最终使得整个数组严格递增且均为正整数，并且要求至少需要改变几个数字

输入:5 1 2 2 3 4

输出:3

这是我尝试过的，每个数字都可以减少更多的a(第一个数字减一，然后第二个数字减二，第三个数字减三)

    #include <stdio.h>
    int Modify_the_array(int B[],int n);
    int max(int a,int b);
    int main(int argc,char *argv) {

        int before_array[]={1,2,3,4,1,2,3,4,5};
        int len=sizeof(before_array[0])/sizeof(before_array);
        int b;
        b=Modify_the_array(before_array,len);
        printf("%d\n",b);
        return 0;
    }

    int max(int a,int b){
        return a>b?a:b;
    }

    int Modify_the_array(int B[],int len) {
        int i,b=0,n=1;
        int maxsofar,tmp,j;
        for (i=0;i<len;i++){
            B[i]=B[i]-n;
            n++;
         }

        maxsofar=0;
        tmp=0;
        for(i=0;i<len;i++) {
            for (j=i+1;j<len;j++) {
            if (B[j]==B[i]&&B[i]>1) {
                maxsofar=max(maxsofar,++tmp);
                b=len-maxsofar;
            }
        }
    }
        return b;
}

有人建议这个问题有另一种解决方案，更有效，任何人都可以给我一些建议，提前感谢

Answer 1

我最近也遇到了同样的问题。澄清一下:

问题陈述

给定一个整数序列 a1,a2,a3.....an。您可以自由地将任何整数替换为任何其他正整数。必须替换多少个整数才能使结果序列严格递增？

输入格式

测试用例的第一行包含一个整数 N - 序列中的条目数。下一行包含 N 个空格分隔的整数，其中第 i 个整数是 ai。

输出格式

输出最少需要替换多少个整数才能使序列严格递增。

根据您的输入，len = 5, arr = [1 2 2 3 4]，减去index+1后，得到[0 0 -1 -1 -1]。

忽略负元素(必须更改这些元素)，计算 Longest Increasing Subsequence (对于这个问题是非递减的)，这是一个经典的动态规划问题。

表示LIS = n的长度(这些元素不会改变)。所以最终的答案(不属于递增子序列和被忽略的负数部分)是len-n(5-2=3)。

我们可以在 O(nlogn) 时间和 O(n) 空间内计算 LIS。

int solve(vector<int> &arr) {
    int len = arr.size();
    for(int i = 0; i < len; i++) {
        arr[i] -= i+1;
    }
    vector<int> lis(len,0);
    int n = 0;
    for(int i = 0; i < len; i++) {
        if(arr[i] >= 0) {
            int pos = binarysearchPos(lis,n,arr[i]);
            lis[pos] = arr[i];
            if(n == pos)
                n++;
        }
    }
    return len-n;
}

int binarysearchPos(vector<int> &arr, int n, int target) {
    if(n == 0)
        return 0;
    if(arr[n-1] <= target)
        return n;
    int low = 0, high = n-1;
    while(low < high) {
        int mid = (low+high)/2;
        if(arr[mid] > target) {
            high = mid;
        } else {
            low = mid+1;
        }
    }
    return low;
}