C语言名题百则之等值数目
文章目錄
已知两个整数数组f[]与g[],它们的元素都已经从小到大排列好,而且两个数组中的元素都各不相同。例如,f[]中有1,3,4,7,9,而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。
就上例而言, f[2]和g[1]为3是一组; f[3]与g[2]为7是第二组
说明: 建议不要使用下面的方法来编程
- 固定f[i]
- 对于f[i]而言,检查g[]中是否有与f[i]相同的元素
- 处理下一个f[i], 即f[i + 1]
因为f[]与g[]都已经从小到大排列好,所以应该活用这一个很强的特性。一个好的程序员绝对不应用上面的笨拙方法来编写程序, 这样会做太多无意义的事。为什么呢?因为g[]的元素都相异,对于f[i]而言,最多只会找出一个与它相同的元素,最坏的情况时把g[]全部查完才找出相同元素(如果采用上面的方法), 如果g[]中有n个元素,需要查n次; 但是若f[]中也有n个元素,那么需要把g[]查n遍,一共作n ** 2(Python的记法,即n的2次方)次比较才能找出结果。
试着找出一种方法,把f[]与g[]各查一次就可以得到答案(记住, 活用f[]与g[]已经从小到大排列的特性).
做完这一题后,建议继续作下一题。
依然是利用已经排好序的这个特性。解答见eq_count.py