加速Swift CodeFight挑战赛
每个Codefighters：
注意:写一个具有O(n)时间复杂度和O(1)额外空间复杂度的解决方案，因为这是你在真实面试中被要求做的事情。
给定一个数组a，它只包含从1到a.length范围内的数字，找出第一个重复的数字，第二次出现的数字具有最小的索引。换句话说，如果有超过1个重复的数字，则返回第二次出现的数字的索引小于第二次出现的另一个数字的索引的数字。如果没有这样的元素，则返回-1。
示例
对于a= 2，3，3，1，5，2，输出应该是firstDuplicate(a) = 3。
有两个重复:数字2和3。第二次出现3的索引比第二次出现2的索引小，所以答案是3。
对于a= 2，4，3，5，1，输出应该是firstDuplicate(a) = -1。
所以这就是我想出来的。它可以工作，但在最终测试中失败，因为它运行了超过4000ms。我坚持我还能做什么。有什么提高速度的想法吗？
func firstDuplicate(a : [Int]) -> Int {
var duplicateIndexArray = [Int]()
for firstIndex in 0..<a.count {
for secondIndex in 0..<a.count {
if a[firstIndex] == a[secondIndex] && firstIndex != secondIndex {
print(firstIndex, secondIndex)
if !(duplicateIndexArray.contains(firstIndex)){
duplicateIndexArray.append(secondIndex)
break
}
}
}
}
// Check for duplicacy
if duplicateIndexArray.count > 0 {
print(duplicateIndexArray)
return a[duplicateIndexArray.min()!]
}
return -1}
回答 3
Stack Overflow用户
发布于 2017-07-22 12:31:54
O(n)时间部分很容易，但是O(1)额外的空间有点棘手。通常，可以使用散列集(在本例中是位数组)来检查一个数字是否多次出现，但这需要O(n)个额外的空间。对于O(1)个额外的空间，我们可以使用源数组本身作为位数组，方法是将其中的一些数字设为负数。
例如，如果数组中的第一个数字是3，那么我们将位置3-1的数字设为负数。如果数组中的其他数字之一也是3，我们可以检查位置3-1的数字是否为负数。
我没有任何使用Swift的经验，所以我将尝试用pseudocode编写一个函数
function firstDuplicate(a)
result = -1
for i = 0 to a.count - 1
if a[abs(a[i])-1] < 0 then
result = a[i]
exit for loop
else
a[abs(a[i])-1] = -a[abs(a[i])-1]
// optional restore the negative numbers back to positive
for i = 0 to a.count - 1
if a[i] < 0 then
a[i] = -a[i]
return resultStack Overflow用户
发布于 2017-07-22 13:29:16
替换此行
for secondIndex in 0..<a.count使用
for secondIndex in firstIndex..<a.count没有重复检查的要求
所以你的最终代码是
func firstDuplicate(a : [Int]) -> Int {
var duplicateIndexArray = [Int]()
for firstIndex in 0..<a.count {
for secondIndex in firstIndex..<a.count {
if a[firstIndex] == a[secondIndex] && firstIndex != secondIndex {
print(firstIndex, secondIndex)
if !(duplicateIndexArray.contains(firstIndex))
{
duplicateIndexArray.append(secondIndex)
break
}
}
}
}
// Check for duplicacy
if duplicateIndexArray.count > 0
{
print(duplicateIndexArray)
return a[duplicateIndexArray.min()!]
}
return -1
}Stack Overflow用户
发布于 2018-04-24 16:35:02
func firstDuplicate(input: [Int]) -> Int{
var map : [String : Int] = [:]
var result = -1
for i in 0 ..< input.count {
if map["\(input[i])"] != nil {
result = i
break
}
else {
map["\(input[i])"] = i
}
}
return result
}https://stackoverflow.com/questions/45250286
复制相似问题
腾讯云开发者
