精华内容
下载资源
问答
  • 算法复杂度分析,算法复杂度o(1), o(n), o(logn), o(nlogn) 时间复杂度On和空间复杂度O1是什么意思?
    展开全文
  • 排序成 100,1,99,2,98,3,......,51,50这样的数列。要求:空间复杂度o(1),时间复杂度o(n)
  • 如果没有要求空间复杂度为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)bool chkPalindrome(ListNode* head) { if (!head || !head-&gt;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)

    题目:在一个长度为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;
                   
        }
    }


    展开全文
  • 如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)   解析: 利用计数排序法,设置一大小为65536的int数组,范围a[0]~a[65535],并初始为0,然后遍历n个数,假设这n个数在数组array
  • 时间复杂度O(1) O(n)表示什么 在刷面试题中的算法题经常出现时间复杂度O(n),空间复杂度O(1)很多时候不知道是什么意思 空间复杂度与时间复杂度是数据结构的复杂度,在现在储存设备越来越便宜的时代,时间复杂度是决定...
  • 一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数. 考虑到平时接触最多的几种排序,时间复杂度都没有O(n)的,看看题目,它也有它的特殊的地方, 待排序...
  • 实现左移指定位数,时间复杂度O(n) ,空间复杂度O(1); 如题,这个算法思想是根据矩阵的逆秩运算得到的。假设我们要处理的串为ab,那么左移一位,也就是把它变成ba。而这不得不使我们联想到矩阵的求逆运算,矩阵...
  • 咋一看会觉得没有办法实现,因为所有的排序方法都无法满足该时间复杂度o(n)和空间复杂度o(1)。 但是如果n是有限的,其实是有办法可解的:假设n 没有超过int的最大值 ,0 可以定义一个大小为65535的数组,遍历n个元素...
  • 49.一道看上去很吓人的算法面试题: 如何对n 个数进行排序,要求时间复杂度O(n),空间复杂度O(1)。
  • //题目:将字符串中的所有空格去掉,要求时间复杂度O(n),空间复杂度O(1) #include &lt;iostream&gt; #include &lt;string.h&gt; #include &lt;assert.h&gt; using namespace std; int ...
  • O(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后面的括号中有一个函数,指明某个算法的耗时或耗空间与数据增长量之间的关系。其中的n代表输入数据的量。x表示数学公式。 时间复杂度和空间复杂度只是描述的角度...哈希算法就是典型的O(1)时间复杂度 O(logn),二...
  • 题目:如何对n个不重复出现的整数序列进行排序,已知这些数的范围为(0-65535),要求时间复杂度O(n),空间复杂度O(1) 分析: 可以申请一个大小为65536的数组A,数组的x下标代表数字x,A[x]代表x 在整数序列中出现的...
  • 面试中经常问的各类算法,比如冒泡算法,堆排序算法,大家可以多关注我们语音分享,都有相关分析,不过还会遇到问是时间复杂度和空间复杂度O(n^2),O(1),这些是什么,一个算法的优劣主要从算法的所需时间和所...
  •  如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)   二,解答  关键:哈希表,空间复杂度O(1)中1的含义(只要是常量就可以)  看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序...
  • 如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) ------------------------------------------ 熟悉排序算法的人知道,目前比较好的排序算法就是快排堆排序归并等等,这些算法也只能让时间复杂度在O...
  • 时间复杂度o(1), o(n), o(logn), o(nlogn)

    千次阅读 2019-10-14 16:51:00
    1、时间复杂度o(1), o(n), o(logn), o(nlogn)。算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn),这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。O后面的括号中有一个函数,...
  • 保证时间复杂度O(n),空间复杂度O(1) 分析步骤: 1、对数组中所有元素求异或,得到结果result。那么由于这个数组中有两个数只出现一次,而其他元素出现两次,所以result的结果一定不为零 2、找出result中任意不为零的...
  • 斐波那契数列 解题思路: 定义三个变量a,b,temp 更新变量a,b public static void main(String[] args) { for(int i=2;i&lt;10;i++){ int num = getNum(i); System.out.print(num+"......
  • 如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) 题目分析: 一、乍一看,不可能完成。时间复杂度为n,纵观所有的排序法,没有达到这个级别的 二、如果针对的是有限个数排列,可以采用标记法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 117,289
精华内容 46,915
关键字:

复杂度o