余数的应用

余数的应用

问题:有一组无重复的整数数列,求其子数列的最大长度,要求子数列中任意两个元素之和都不能整除k。

例1:

数列S=[19, 10, 12, 24, 25,22] k=4

其中一个子数列s1=[10,12,25],另一个s2=[19,22,24],其最大的长度是3,所以程序返回3.

例2:

数列S=[1, 7, 2, 4] k=3

1+7=8
1+2=3
7+2=9
7+4=11
2+4=6

只有当子数列s1=[1, 7, 4]时满足题目要求,不能整除k。

def nonDivisibleSubset(k, s):
    if k==1:
        return 1
    else:
        s_arr=[0]*k
        for i in s:
            s_arr[i%k]+=1
        result = 1 if s_arr[0]>=1 else 0
        for i in range(1,k//2+1):
            if (2*i)%k!=0:
                result+=(s_arr[i] if s_arr[i]>s_arr[-i] else s_arr[-i])
            else:
                result+=1
        return result

其解法我也是看了别人的方法有了灵感:

  1. 根据题目要求任意两个数不能整除k,也就是这两个数的余数之和也不能整除k。(这是本题的核心,因为如果用枚举比对的话,当数列长度为10^5时,比对时间太长了,时间复杂度…我不会算,总之很长:(。因为每次在子数列中加入一个元素时都要比对整个子数列是否满组条件。)
  2. 任意整数整除k的余数一共有k个可能性,0~k-1
  3. 把数列中的元素按其余数分成k组“存入”s_arr(其实s_arr中只是记录了每个余数有多少个元素,并没有真正的转存原始数列元素),因为只需要把分组中的元素当成一个数来看待就可以
  4. 这时会发现(s_arr[i]+s_arr[-i])%k==0,所以s_arr[i]和s_arr[-i]的元素不能同时存在于子数列中,这样会违背条件。所以在统计结果时要在range(1,k//2+1)这个范围。在加入子数列时判断一下是s_arr[i]中的元素多还是s_arr[-i]的元素多,把元素多的加入到子数列中。
  5. s_arr[0]中的元素只能看做一个元素,因为其中如果有多个元素的话,两个s_arr[0]中的元素相加后再整除k,结果依然是0。这也解释了为什么要做(2*i)%k!=0的判断,因为(2*i)%k==0代表(s_arr[i][x]+s_arr[i][x])%k==0

Comments are closed.