最近我遇到了一个问题,要求在没有任何额外缓冲区的情况下找出字符串中的非唯一字符.我将此问题解释为字符串中的字符的就地排序,然后迭代它以便跟踪非唯一字符.
另一个可以具有O(1)空间和O(n ^ 2)运行时间的解决方案是在字符串上有两个"for"循环来跟踪常见的任何字符对.
我需要的是用O(1)空格在至少O(nlogn)时间对字符串进行排序.
是否有一种简单/优雅的方法在O(nlgn)中使用O(1)空间进行就地排序的字符？
假设我想从字符串中删除重复项.我决定使用长度为256的布尔数组来存储特定字符是否已经出现.我可以遍历字符串,并可以借助此辅助布尔数组删除所有重复项.
我的问题是"这个算法是否就位？"
我认为它使用的是恒定的空间量,它不会随着它应该就地输入的大小而改变.如果我错了,请纠正.
我正在编写一个Queue包含大多数操作列表的类.但是我不会从中升级list,因为我不想提供所有的list API's.我的代码粘贴在下面.该add方法似乎工作正常,但iadd似乎出错,它打印没有.这是代码:
import copy
from iterator import Iterator
class Abstractstruc(object):
def __init__(self):
assert False
def __str__(self):
return "<%s: %s>" %(self.__class__.__name__,self.container)
class Queue(Abstractstruc,Iterator):
def __init__(self,value=[]):
self.container=[]
self.size=0
self.concat(value)
def add(self, data):
self.container.append(data)
def __add__(self,other):
return Queue(self.container + other.container)
def __iadd__(self,other):
for i in other.container:
self.add(i)
def remove(self):
self.container.pop(0)
def peek(self):
return self.container[0]
def __getitem__(self,index):
return self.container[index]
def __iter__(self):
return Iterator(self.container)
def concat(self,value):
for i in value:
self.add(i)
def __bool__(self):
return len(self.container)>0 …数组yn并且zn等于数字,但有一个奇怪的区别:yn += 7正如预期的那样,行不会改变tn数组,但第二行最后一行会zn += 7改变tn数组!
这是代码:
import numpy as np
def f(x): return (1*x)
def g(x): return (x)
nn = 5
tn = np.zeros(nn)
yn = np.zeros(nn)
zn = np.zeros(nn)
tn = np.linspace(0,1,nn)
yn = f(tn)
zn = g(tn)
print('tn at step1 =',tn)
yn += 7 #as expected, this line does not change tn.
print('tn at step2 =',tn)
zn += 7 #why this line adds 7 to tn …我一直在研究排序算法.到目前为止,我发现的所有排序算法要么依赖于已知长度(几乎所有排序算法.我不能使用它们,因为"正确"长度是O(n)),或者比快速排序慢(例如插入分类).
在Lua中,有两个长度概念:
我已经研究过heapsort,但是heapsort需要构建一个堆,然后排序.它不能同时作为单个操作,这意味着它仍然存在O(n)长度问题.
使用插入排序,您只需运行插入排序算法,直到您点击第一个nil.这只排序表的"正确序列"部分(即,从1到n的键没有任何nil值),但插入排序比quicksort慢.
是否有任何就地排序算法,如插入排序,不依赖于长度,但性能可与快速排序相媲美？
示例插入排序代码(在维基百科的帮助下):
function isort(t)
-- In-place insertion sort that never uses the length operator.
-- Stops at the first nil, as expected. Breaks if you use "for i = 1, #t do"
for i in ipairs(t) do
local j = i
while j > 1 and t[j-1] > t[j] do
t[j], t[j-1] = t[j-1], t[j]
j = j - 1
end
end
end
local …