某顺序表L中存放整型数据,编写算法,在时间复杂度O(n) 、空间复度 O(1)内,对表L进行重新排序,将奇数全部放在前面,偶数全部放在后面。
时间: 2023-04-01 10:04:02 浏览: 128
可以使用双指针法,一个指针从表头开始,一个指针从表尾开始,分别向中间移动。当左指针指向偶数,右指针指向奇数时,交换两个数的位置。直到左指针和右指针相遇为止,这样就可以将奇数全部放在前面,偶数全部放在后面。时间复杂度为O(n),空间复杂度为O(1)。
相关问题
用c语言编写算法:某顺序表L中存放整型数据,编写算法,在时间复杂度O(n) 、空间复度 O(1)内,对表L进行重新排序,将奇数全部放在前面,偶数全部放在后面。
可以使用双指针法,一个指针从表头开始,一个指针从表尾开始,分别向中间移动。当左指针指向偶数,右指针指向奇数时,交换两个数的位置。直到左指针和右指针相遇为止,即可完成表L的重新排序。这个算法的时间复杂度为O(n),空间复杂度为O(1)。
在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是( )
1. 读取某个已知下标位置的元素
2. 修改某个已知下标位置的元素
3. 在表尾插入一个元素
4. 在表头插入一个元素
5. 在某个已知下标位置插入一个元素
6. 删除某个已知下标位置的元素
7. 获取表的长度
8. 判断表是否为空
根据题意,需要选择时间复杂度为O(1)的操作,因此正确答案是:1、2、3、4、5、6、7、8。