数组中重复数字时间复杂度O(N)，空间复杂度O(1)【C++】

雨点打透心脏的1/2处 2022-05-08 06:54 413阅读 0赞

在这里插入图片描述
在这里插入图片描述

  1. #include <iostream>
  3. bool duplicate(int numbers[], int length, int * duplication){
  4.     if(numbers == nullptr || length <= 0){
  5.         return false;
  6.     }
  7.     for(int i = 0;i < length;i ++){
  8.         if(numbers[i] < 0 || numbers[i] > length - 1)
  9.             return false;
  10.     }
  11.     for(int i = 0;i < length;i ++){
  12.         while(numbers[i] != i){
  13.             if(numbers[i] == numbers[numbers[i]]){
  14.                 * duplication = numbers[i];
  15.                 return true;
  16.             }
  17.             int temp = numbers[i];
  18.             numbers[i] = numbers[temp];
  19.             numbers[temp] = temp;
  20.         }
  21.     }
  22.     return false;
  23. }
  25. int main(int argc, const char * argv[]) {
  26.     int numbers[] = {3, 1, 2, 0, 2, 5, 3};
  27.     int dup;
  28.     if(duplicate(numbers, 7, & dup)){
  29.         std::cout << dup << std::endl;
  30.     }
  31. }

发表评论

表情：
评论列表 （有 0 条评论，413人围观）

还没有评论，来说两句吧...

相关阅读

    相关 时间复杂度_空间复杂度

    时间复杂度\_空间复杂度 主要说明以下3点： 1.算法效率 2.时间复杂度 3.空间复杂度 一、算法效率 算法效率分析分为两种：第一种是时间效率，第二种

    朱雀朱雀/ 0 赞/ 301 阅读

    相关 时间复杂度和空间复杂度

    算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 （1）时间频度  一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可

    秒速五厘米秒速五厘米/ 0 赞/ 409 阅读

    相关 时间复杂度和空间复杂度

    一、为什么要研究时间和空间复杂度     假设计算机是无限快的并且计算机存储器是免费的的，你还有什么理由来研究算法吗？即使只是因为你还想证明你的解法会终止并以正确的答案终

    灰太狼灰太狼/ 0 赞/ 562 阅读