sicp每日一题[2.62]

Exercise 2.62

Give a (n) implementation of union-set for sets represented as ordered lists.

这道题难度也不大，思路是依次从两个集合中取第一个元素，比较他们的大小，把小的那个和剩下所有元素连接的结果连接起来。由于两个集合中每个元素都只需要取出一次，所以时间复杂度应该是 O(n)。

(define (union-set set1 set2)(cond ((null? set1) set2)((null? set2) set1)((let ((s1 (car set1))(s2 (car set2)))(if (<= s1 s2)(cons s1 (union-set (cdr set1) set2))(cons s2 (union-set set1 (cdr set2))))))))(define set1 (list 1 3 5 7 9))
(define set2 (list 2 4 6 8 10))(union-set set1 set2); 结果如下所示
'(1 2 3 4 5 6 7 8 9 10)