-
算法复杂度分析,算法复杂度o(1), o(n), o(logn), o(nlogn) 时间复杂度On和空间复杂度O1是什么意思?
2020-06-23 21:43:03算法复杂度分析,算法复杂度o(1), o(n), o(logn), o(nlogn) 时间复杂度On和空间复杂度O1是什么意思?展开全文 -
使用空间复杂度o(1),时间复杂度o(n)算法进行排序
2017-06-23 07:11:55排序成 100,1,99,2,98,3,......,51,50这样的数列。要求:空间复杂度o(1),时间复杂度o(n) -
单链表归并排序——时间复杂度O(nlogn),空间复杂度O(1)
2018-03-31 23:33:26如果没有要求空间复杂度为O(1),可以遍历链表并将每个节点的值存入vector中,利用...时间复杂度O(nlogn),空间复杂度O(n)。 考点: 1. 归并排序O(nlogn);2. 快慢指针定位链表中间节点。 复杂度分析: T(n) ...如果没有要求空间复杂度为O(1),可以遍历链表并将每个节点的值存入vector中,利用sort( )对vector排序后,最后再遍历一次链表,将排序后的vector中的元素依次赋给链表的节点值。时间复杂度O(nlogn),空间复杂度O(n)。
考点:
1. 归并排序O(nlogn);2. 快慢指针定位链表中间节点。复杂度分析:
T(n) 拆分 n/2, 归并 n/2 ,一共是n/2 + n/2 = n
/ \ 以下依此类推:
T(n/2) T(n/2) 一共是 n/2*2 = n
/ \ / \
T(n/4) ……….. 一共是 n/4*4 = n一共有logn层,故复杂度是 O(nlogn)
#include <iostream> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* mergeSort(ListNode* left, ListNode* right) { //merge时,只改变节点的指向,无需改变任何一个节点的内部值。 if (left == nullptr && right == nullptr) return nullptr; ListNode duyy(0); ListNode *temp = &duyy; while (left != nullptr && right != nullptr) { if (left->val > right->val) { temp->next = right; right = right->next; } else { temp->next = left; left = left->next; } temp = temp->next; } if (left != nullptr) temp->next = left; if (right != nullptr) temp->next = right; return duyy.next; } ListNode* sortList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* fast = head->next; ListNode* slow = head; while (fast != nullptr && fast->next != nullptr) { //快慢指针定位链表中间节点 slow = slow->next; fast = fast->next->next; } ListNode *left = sortList(slow->next); slow->next = nullptr; //将中间节点的下一个节点指向空,用于merge时表示链表的终点。 ListNode* right = sortList(head); return mergeSort(left, right); //**此处一定是使用sortList()返回的left和right指针**。 } int main() { int n; cin >> n; ListNode *head = new ListNode(0); ListNode *curr = head; for (int i = 0; i < n; i++) { int a; cin >> a; ListNode *temp = new ListNode(a); curr->next = temp; curr = temp; } head = sortList(head->next); while (head != nullptr) { cout << head->val << " "; head = head->next; } return 0; }
-
链表的回文结构,时间复杂度O(n),空间复杂度O(1)
2018-04-10 15:29:33链表的回文结构链表的回文结构,时间复杂度O(n),空间复杂度O(1)bool chkPalindrome(ListNode* head) { if (!head || !head->next) return true; ListNode *slow = head, *fast = head; while (fast-&...链表的回文结构
链表的回文结构,时间复杂度O(n),空间复杂度O(1)
bool chkPalindrome(ListNode* head) { if (!head || !head->next) return true; ListNode *slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } ListNode *last = slow->next, *pre = head; while (last->next) { ListNode *tmp = last->next; last->next = tmp->next; tmp->next = slow->next; slow->next = tmp; } while (slow->next) { slow = slow->next; if (pre->val != slow->val) return false; pre = pre->next; } return true; }
-
返回数组中任意某个重复的数字--时间复杂度O(n)空间复杂度O(1)
2017-03-12 19:54:21返回数组中任意某个重复的数字--时间复杂度O(n)空间复杂度O(1)题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
思路分析:
思路1:将数组排序,然后遍历数组每次判断当前元素和下一个元素如果相等则返回。时间复杂度排序O(nlogn).
思路2:用hash表,比如用数组,初始化一个大小为N的数组为0,遍历寻找的数组,找到元素值为下标的位置置1.找到第二个同样元素时候,发现是1,则返回该元素。比如:遍历numbers[3]===5, 判断辅助数组a[5]是否为0,如果为0,说明是第一次找到5,置1.后面再找到numbers[8]==5,此时准备将辅助数组a[5]置1,发现已经是1,则找到重复元素。时间复杂度O(n),空间复杂度O(n).【数组可以模拟简单的hash表,标记法】
思路3:时间复杂度O(n),空间复杂度O(1)。由于数组的值都在0----n-1之间,如果排序后,应该有些位置有相同元素或者有一个元素出现在两个位置,扫描遍历数组,当numbers[i]!=i, 说明该元素应该出现在下标为numbers[i]的位置,当 numbers[i]!=numbers[numbers[i]],交换,当numbers[i] ==numbers[numbers[i]]则找到两个位置有同样的数组,返回。
java实现代码如下:
public class Solution { // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation; // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++ // 这里要特别注意~返回任意重复的一个,赋值duplication[0] // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false public boolean duplicate(int numbers[],int length,int [] duplication) { //异常处理 if(numbers==null || length<0) return false; for(int number:numbers) if(number<0 || number>length-1) return false; for(int i=0;i<length;i++){ while(numbers[i]!=i){ if(numbers[i]==numbers[numbers[i]]){ duplication[0]=numbers[i]; return true; } //交换 int temp=numbers[numbers[i]]; numbers[numbers[i]]=numbers[i]; numbers[i]=temp; } } return false; } }
-
计数排序算法,时间复杂度O(n),空间复杂度O(1)
2015-08-16 11:05:06如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) 解析: 利用计数排序法,设置一大小为65536的int数组,范围a[0]~a[65535],并初始为0,然后遍历n个数,假设这n个数在数组array -
PHP 算法 时间复杂度O(1) O(n)表示什么 空间复杂度
2020-09-16 18:02:55时间复杂度O(1) O(n)表示什么 在刷面试题中的算法题经常出现时间复杂度O(n),空间复杂度O(1)很多时候不知道是什么意思 空间复杂度与时间复杂度是数据结构的复杂度,在现在储存设备越来越便宜的时代,时间复杂度是决定... -
时间复杂度O(n),空间复杂度O(1)的排序
2013-10-24 10:44:54一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数. 考虑到平时接触最多的几种排序,时间复杂度都没有O(n)的,看看题目,它也有它的特殊的地方, 待排序... -
实现左移指定位数,时间复杂度O(n) ,空间复杂度O(1)
2015-06-17 00:49:20实现左移指定位数,时间复杂度O(n) ,空间复杂度O(1); 如题,这个算法思想是根据矩阵的逆秩运算得到的。假设我们要处理的串为ab,那么左移一位,也就是把它变成ba。而这不得不使我们联想到矩阵的求逆运算,矩阵... -
如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)
2016-10-31 10:41:45咋一看会觉得没有办法实现,因为所有的排序方法都无法满足该时间复杂度o(n)和空间复杂度o(1)。 但是如果n是有限的,其实是有办法可解的:假设n 没有超过int的最大值 ,0 可以定义一个大小为65535的数组,遍历n个元素... -
第四十九题(排序,要求时间复杂度O(n),空间复杂度O(1))
2014-07-10 17:00:1949.一道看上去很吓人的算法面试题: 如何对n 个数进行排序,要求时间复杂度O(n),空间复杂度O(1)。 -
【面试题】将字符串中的所有空格去掉,要求时间复杂度O(n),空间复杂度O(1)
2018-04-06 21:35:15//题目:将字符串中的所有空格去掉,要求时间复杂度O(n),空间复杂度O(1) #include <iostream> #include <string.h> #include <assert.h> using namespace std; int ... -
时间复杂度/空间复杂度O(1)、O(n)
2020-09-07 16:05:23O(x):表示算法时空(时间/空间)的复杂度 O括号里的函数 x 表示:某个算法的耗时/耗空间与数据增长量之间的关系。其中O(n),O(n^2)等的 n 表示输入数据的量 2.O(1) O(1),即是最低的时空复杂度。即,耗时/耗空间与... -
时间复杂度O(1) O(n)表示什么
2020-06-21 20:48:44时间复杂度O(1) O(n)表示什么 在刷面试题中的算法题经常出现时间复杂度O(n),空间复杂度O(1)很多时候不知道是什么意思 空间复杂度与时间复杂度是数据结构的复杂度,在现在储存设备越来越便宜的时代,时间复杂度是决定... -
时间复杂度或空间复杂度O(x,n)
2020-02-28 08:36:59O后面的括号中有一个函数,指明某个算法的耗时或耗空间与数据增长量之间的关系。其中的n代表输入数据的量。x表示数学公式。 时间复杂度和空间复杂度只是描述的角度...哈希算法就是典型的O(1)时间复杂度 O(logn),二... -
如何对n个整数数进行排序,要求时间复杂度O(n),空间复杂度O(1)
2013-11-29 13:36:08题目:如何对n个不重复出现的整数序列进行排序,已知这些数的范围为(0-65535),要求时间复杂度O(n),空间复杂度O(1) 分析: 可以申请一个大小为65536的数组A,数组的x下标代表数字x,A[x]代表x 在整数序列中出现的... -
算法面试中 时间复杂度和空间复杂度 o(n) o(logn) 是什么?
2020-01-14 17:24:54面试中经常问的各类算法,比如冒泡算法,堆排序算法,大家可以多关注我们语音分享,都有相关分析,不过还会遇到问是时间复杂度和空间复杂度O(n^2),O(1),这些是什么,一个算法的优劣主要从算法的所需时间和所... -
【100题】第四十九题 排序,要求时间复杂度O(n),空间复杂度O(1)
2012-08-21 00:25:26如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) 二,解答 关键:哈希表,空间复杂度O(1)中1的含义(只要是常量就可以) 看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序... -
算法习题49:如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)
2013-11-07 13:07:51如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) ------------------------------------------ 熟悉排序算法的人知道,目前比较好的排序算法就是快排堆排序归并等等,这些算法也只能让时间复杂度在O... -
时间复杂度o(1), o(n), o(logn), o(nlogn)
2019-10-14 16:51:001、时间复杂度o(1), o(n), o(logn), o(nlogn)。算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn),这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。O后面的括号中有一个函数,... -
如何快速找出一个数组中只出现一次的两个数,其他元素出现两次?保证时间复杂度O(n),空间复杂度O(1)
2017-09-29 21:51:16保证时间复杂度O(n),空间复杂度O(1) 分析步骤: 1、对数组中所有元素求异或,得到结果result。那么由于这个数组中有两个数只出现一次,而其他元素出现两次,所以result的结果一定不为零 2、找出result中任意不为零的... -
斐波那契数列 时间复杂度O(n) 空间复杂度O(1)
2018-12-28 20:15:53斐波那契数列 解题思路: 定义三个变量a,b,temp 更新变量a,b public static void main(String[] args) { for(int i=2;i<10;i++){ int num = getNum(i); System.out.print(num+"...... -
数据结构——算法之(017)( 如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1))
2014-05-25 20:51:56如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) 题目分析: 一、乍一看,不可能完成。时间复杂度为n,纵观所有的排序法,没有达到这个级别的 二、如果针对的是有限个数排列,可以采用标记法...