计数数组中的不同切片

Question

我试图解决这个问题。

给出了一个整数M和一个由N个非负整数组成的非空零索引数组A。数组A中的所有整数都小于或等于M。

一对整数（P，Q），使得0≤ P≤ Q

例如，考虑整数M=6和数组A，这样：

A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2 

正好有九个不同的切片：（0, 0), (0, 1), (0, 2), (1, 1), (1,2), (2, 2), (3, 3), (3, 4)和（4,4）。

目标是计算不同切片的数量。

提前感谢。

#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 100002

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

using namespace std;

bool check[MAX];

int solution(int M, vector<int> &A) {
    memset(check, false, sizeof(check));
    int base = 0;
    int fibot = 0;
    int sum = 0;

    while(fibot < A.size()){

        if(check[A[fibot]]){
            base = fibot;
        }

        check[A[fibot]] = true;

   sum += fibot - base + 1;
        fibot += 1;  
    }

    return min(sum, 1000000000);
}

Answer 1

我想分享我用C语言实现的算法的解释，然后是实际实现。

1. 请注意，由于每个元素都是一个不同的一项切片，因此不同切片的最小数量为N

这个解决方案的运行时复杂性是O（N），因为我们要遍历每个元素。

这个解决方案的空间复杂度是O（M），因为我们有一个散列来存储序列中出现的元素。此哈希的最大元素是M。

int solution(int M, vector<int> &A)                                             
{                                                                               
  int N = A.size();                                                             
  int distinct_slices = N;                                                      
  vector<bool> seq_hash(M + 1, false);                                          
  for (int back = 0, front = 0; front < N; ++back) {                            
    while (front < N and !seq_hash[A[front]]) { distinct_slices += front - back; if (distinct_slices > 1000000000) return 1000000000; seq_hash[A[front++]] = true; }
    while (front < N and back < N and A[back] != A[front]) seq_hash[A[back++]] = false;
    seq_hash[A[back]] = false;                                                  
  }                                                                             
                                                                                
  return distinct_slices;                                                       
}

Answer 2

100%python解决方案帮助了我，这要感谢https://www.martinkysel.com/codility-countdistinctslices-solution/

def solution(M, A):
    
        the_sum = 0
    
        front = back = 0
    
        seen = [False] * (M+1)
    
        while (front < len(A) and back < len(A)):
    
            while (front < len(A) and seen[A[front]] != True):
    
                the_sum += (front-back+1)
    
                seen[A[front]] = True
    
                front += 1
    
            else:
    
                while front < len(A) and back < len(A) and A[back] != A[front]:
    
                    seen[A[back]] = False
    
                    back += 1
    
                seen[A[back]] = False
    
                back += 1
                   
        return min(the_sum, 1000000000)  
           

Answer 3

解决方案不正确是因为你的算法错了。

首先，让我给你看一个反例。设A={2，1，2}。第一次迭代：base=0，fibot=0，sum=1 没错。第二个：base=0，fibot=1，sum=2。这也是正确的。最后一步：fibot=2，check[A[fibot]]为true，因此，base=2。但它应该是1。因此，您的代码返回的是正确答案，而您的代码返回的是正确答案。

正确的方法可能是这样的：从L=0开始。对于从0到n-1的每个R，请将L一直向右移动，直到子数组只包含不同的值（您可以保持数组中每个值的出现次数，并使用这样一个事实，即A[R]是唯一可以出现多次的元素）。

您的代码还有一个问题：如果测试平台上的int是32位类型（例如，如果A的所有元素都不同），那么sum变量可能会溢出。

至于你的算法为什么不正确的问题，我不知道为什么它首先应该是正确的。你能证明吗？在我看来，base=fibot的赋值非常随意。