查找是否存在重复存在的SML NJ [英] Find if Duplicates Exist SML NJ

问题描述

我想编写一个搜索列表的单个函数，并查找此列表中是否有重复值。该函数应该返回一个布尔值。这是我在哪里，但这不工作......

I want to write a single function that searches a list and finds if there are any duplicates values in this list. The function should return a boolean. Here is where I'm at, but this is not working...

fun myFunc [] = true
myFunc(x::xs) = 
if(x=myFunc(xs)) then false
else myFunc(xs);

[1,2,2,3,4,5,6] should return true
[1,2,3,4,5,6,7] should return false
[1,2,3,4,5,6,1] should return true

谢谢！@ b $ b

thanks!

推荐答案

关于你的函数，你不能比较 x 和 myFunc xs ，因为它们可能不具有相同的类型。而空列表是一个没有重复的列表（ myFunc [] 应该返回 false ）。

Regarding your function, you cannot compare x and myFunc xs since they may not have the same type. And empty list is a list without duplication (myFunc [] should return false).

这是有效的：

This works:

fun duplicated [] = false
  | duplicated (x::xs) = (List.exists (fn y => x = y) xs) orelse (duplicated xs)

然而，最坏情况下的时间复杂度是O（n <2>）（ n 是列表的长度），这是相当低效的。

However, the worst-case time complexity is O(n²) (n is the length of the list) which is quite inefficient.

这篇关于查找是否存在重复存在的SML NJ的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！