【以下内容仅为本人在学习中的所感所想,本人水平有限目前尚处学习阶段,如有错误及不妥之处还请各位大佬指正,请谅解,谢谢!】
!!!观前提醒!!!
【本文内容可能较为复杂,虽然我已经以较为清晰的方式展现我的思想,但可能依旧容易引起思维混乱,若感到混乱或不舒服的情况,可直接转跳至文末的总结处;也可以先看完结论再来阅读文章】
引言
List作为一种动态存储结构,可以代替数组,还可以将其当作链表使用。本文将介绍C#中List的相关内容,重点介绍其包含的Contains与Equals方法,并针对集合的比较与去重进行分析,提供可行的解决方案。
起因
题目链接:6049. 含最多 K 个可整除元素的子数组 - 力扣(LeetCode) (leetcode-cn.com)
实际上就是在一个数组的所有非空“子数组”中,统计其中满足要求的子数组的数量。
经过与结果
想法:枚举每一个子数组,判断其是否符合要求;若符合则判断该子数组是否应经被统计过;未统计则加入,已统计则跳过。
结果:(我真的是匪夷所思啊!!!)
【注:将HashSet换为List运行结果相同】
当换用字符串为元素后,结果却没有问题且AC通过
【注:此部分属于介绍内容,非本文重点,可转跳至第二部分】
在分析上面问题之前,我们先对List有一个认知。List是一个C#中最常见的可伸缩数组组件,即动态数据存储结构。我们常常用它来替代数组,并且因为它的长度是动态的,所以我们在写的时候不用手动去分配的大小;甚至有时我们也会拿它当链表使用。
属性
(一)Count
定义:获取 List<T>中包含的元素数。
(二)Capacity
(1)定义:获取或设置该内部数据结构在不调整大小的情况下能够容纳的元素总数。
(2)可能触发的异常:
ArgumentOutOfRangeException:Capacity 被设置为一个小于现有长度的值。
OutOfMemoryException:系统上没有足够的可用内存。
小结
(1)Capacity是可能需要调整大小之前存储的元素数目,以4为基数,每次递增4;Count是实际位于其中List<T>元素的数目。
(2)Capacity始终大于等于Count。如果在添加元素时Count超过Capacity,则会在添加元素前自动重新分配Capacity的值;在清空List<T>或删除元素后Capacity的值不会变化。
(3)可通过TrimExcess()方法删除多余的预留空间,即使Capacity的值等于Count的值。
(3)获取此属性的值的运算时间复杂度为 O(1)。
(三)Item[index]
(1)定义:获取或设置指定索引处的元素。
(2)可能触发的异常:
ArgumentOutOfRangeException:index小于0或大于等于 Count。
常用方法
(一)添加
(1)Add(T) 将对象添加到末尾
(2)AddRange(List<T>) 将集合添加到末尾【注:List<T>非空】
(3)Insert(int index, T) 将元素插入指定索引处
(4)InsertRange(int index, List<T>) 将集合插入指定索引处【注:List<T>非空】
(二)删除
(1)Remove(T) 移除指定对象的第一个匹配项
(2)RemoveAll(Predicate<T> match) 移除与match相匹配的所有元素
(3)RemoveAt(int num) 移除指定s索引处的元素
(4)RemoveRange(int index, int count) 移除指定范围内的元素
(三)查找
(1)Find(Predicate<T> match) 搜索并返回第一个与match相匹配的元素
(2)FindIndex(Predicate<T> match) 返回第一个与match相匹配的元素的索引值
(3)FindIndex(int startIndex, Predicate<T> match) 从startIndex开始搜索,返回第一个与match相匹配的元素的索引值
(4)FindIndex(int startIndex, int count, Predicate<T> match) 从startIndex开始搜索count位,返回第一个与match相匹配的元素的索引值
【注:FindLast、FindLastIndex从后往前搜索,其余部分相同】
(5)IndexOf(T) 搜索指定对象,返回第一个匹配项从零开始的索引
(6)Find(T, int index) 在[index, count)范围内搜索指定对象,返回第一个匹配项从零开始的索引
(7)Find(T, int index, int count) 在[index, index + count]范围内搜索指定对象,返回第一个匹配项从零开始的索引
(四)排序
(1)Sort() 使用默认比较器(升序)对List进行排序
(2)Sort(IComparer<T>) 使用指定比较器对List进行排序
(3)Sort(int index, int count, IComparer<T>) 在指定范围内使用指定比较器(不写,则为默认比较器)对List进行排序
(一)包含——Contains
【注:元素之间的比较较为简单,在此不做叙述】
C#中变量可分为值类型和引用类型。值类型储存在栈中,引用类型储存在堆中,引用类型的内存地址储存在栈中。其中:泛型List的Contains在比较值类型时,直接比较值,但在比较引用类型时,比较的是引用地址。
虽然明白了Contains的比较原理,但这时候又出现了一个问题:List<T>是引用类型,string也是引用类型,那为什么在判断string是否相同时可以达到预期效果而判断List<T>时不能达到预期效果呢?针对这个问题,我们直接查看一下这两个类型所声明的变量的内存地址。
(1) 泛型类型为List<T>【此时,内部储存的元素为集合】
可以发现:
a. 两个字符串值相同,则其内存地址相同
b. 两个List<T>值相同,但其内存地址不同
c. 当泛型类型为集合时,即使两个集合中储存的元素值相同且元素内存地址相同,但这两个集合本身的内存地址不同,即list1的地址不同于list2。而根据Contains的查找规律,无法将这两个集合视为同一个集合。
所以我们所认为的集合相同是内部元素相同,而C#所认为的集合相同是内存地址的相同。
(2)泛型类型为string【此时,内部储存的元素为字符串】
内部元素不同:
内部元素相同:
可以发现:
a. 两个字符串值相同,则其内存地址相同
b. 当泛型类型为字符串时,只有两个字符串的内存地址相同,即str1的地址等同于str2,所以可将这两个元素视为同一个元素。
(3)泛型类型为自定义类型【此时,内部储存的元素为自定义对象】
通过上面这个例子可以发现:
a. 两个自定义对象值相同,但其内存地址不同
b. 对象再传递时,传递的是内存地址
c. 当泛型类型为自定义对象类型时,只有两个对象的内存地址相同时,才判定这两个对象是同一个对象。
小结
至此,我们得出List. Contains()方法的执行原理:
a. 在查找是否包含时,查找的是针对定义的泛型T,所存储的对象,与对象中再存储的元素无关。
b. 在查找是否包含值类型时,直接比较值;查找引用类型时,先比较内存地址,若内存地址相同则返回True;否则再比较值。
(二)比较——Equals
(1)泛型类型为List<T>【此时,内部储存的元素为集合】
(2)泛型类型为string【此时,内部储存的元素为字符串】
内部元素不同:
内部元素相同:
直接使集合本身相同:
(3)泛型类型为自定义类型【此时,内部储存的元素为自定义对象】
小结
a. 通过以上两个例子,我们可以总结出List. Equals()方法的执行原理:在比较值类型时,直接比较值;在比较引用类型时,只比较内存地址。
回到开头的题目
为什么第一种方法是错的,因为执行Contains操作的对象是是两个集合,虽然两个集合内部存储元素相同,但两个集合本身的内存地址是不同的,所以总会被判定为是不同的元素,因而不能用于判重;
第二种方法使用字符串,操作对象即为字符串,相同的字符串值,内存地址相同,所以可以用来判重。
a. 不论是Contains方法还是Equals方法,首先要明确操作的对象,即要查找或比较的是哪两个对象。
b. 确定对象后,判断其内存地址是否相同,相同返回True,不同返回False。
c. 一般地,引用类型传递时,传递的是内存地址,且相同值的引用类型内存地址不同;特别地,当字符串值相同时,内存地址也相同。
【感谢您可以抽出时间阅读到这里,第一篇博客可能会有许多不妥之处;受限于水平,许多地方可能存在错误,还请各位大佬留言指正,请见谅,谢谢!】
#附本题代码
模拟 + 哈希去重
public class Solution { public int CountDistinct(int[] nums, int k, int p) { int res = 0; HashSet<string> set = new HashSet<string>(); for (int i = 0; i < nums.Length; i++) { int cnt = 0; StringBuilder builder = new StringBuilder(); for (int j = i; j >= 0; j--) { builder.Append(nums[j] + " "); if (nums[j] % p == 0) cnt++; if (cnt <= k && !set.Contains(builder.ToString())) { set.Add(builder.ToString()); res++; } } } return res; } }