1
會是什麼樣的複雜性（大O符號）以下功能：尋找複雜 - 斯威夫特
func sortList(_ thresholdValue: Int) -> [Int] {
var currentValue = thresholdValue
//Values is an array of integers - [Int]
var valArr = values.sorted { $0 > $1 } //should be a merge sort O(nlogn)
for i in 0...valArr.count-1 {
if valArr[i] < currentValue {
currentValue = currentValue - valArr[i]
} else {
let tempArr = filter(valArr[0...i-1], currentValue) // O(n) - array splicing
if tempArr.count > 0, let updatedValue = tempArr.first {
currentValue = currentValue - updatedValue
valArr = updateArr(array: valArr, fromIndex: valArr.index(of: updatedValue)!, toIndex: i)
currentValue = thresholdValue
} else {
currentValue = thresholdValue - valArr[i]
}
}
}
return valArr
}
func updateArr<T>(array: Array<T>, fromIndex: Int, toIndex: Int) -> Array<T>{
var arr = array
let element = arr.remove(at: fromIndex) // O(n)
arr.insert(element, at: toIndex) // O(n)
return arr
}
func filter(_ tempArr:ArraySlice<Int>,_ currentValue : Int) -> [Int]{
for value in tempArr { // O(n)
if let index = values.index(of: value) {
tempArr.remove(at: index) // O(n)
}
}
return tempArr.filter { $0 <= currentValue }.sorted { $0 > $1 } //O(n) O(mlogm)
}
上述函數試圖重新排列的整數，以致元素的序列（而不是子陣列）總計小於或等於k的值。一旦序列完成，一個新的序列（在同一個陣列中）的總和小於或等於k。我爲每個可能的執行添加了可能的複雜性（不是O（1））。