剑指offer----C语言版----第一天

目录

1. 数组中重复的数字Ⅰ

 1.1 题目描述

1.2 思路一

1.3 思路二

 1.4 思路三（最优解）

1. 数组中重复的数字Ⅰ

原题：剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

 1.1 题目描述

给你一个数组，大小为N，数组里面的值的介于 [ 0, N-1 ]，要求你找出数组中任意一个重复的数字。

1.2 思路一

 我们选用一个时间复杂度为O(N*logN)的排序算法对数组进行排序，例如快速排序，堆排序，归并排序。然后再去遍历排序好的数组，找出重复的数字。解题的时间复杂度：O(N*logN)，空间复杂度：O(1)。

我这里自己写了快速排序的代码，如果大家嫌麻烦可以使用C语言的库函数qsort来对数组进行排序，底层逻辑也是快速排序，但是在数据量比较小的时候用的是插入排序，库函数嘛，效率的优化是最高的。

cplusplus.com - The C++ Resources Networkhttps://legacy.cplusplus.com/大家可以使用这个来查看C语言的标准库函数。

  

   

    

     

    
    

     

      //数字交换
     
    
   

    

     

    
    

     

      void Swap(int* pa, int* pb)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    
      int temp =*pa;
     
    
   

    

     

    
    

     

          *pa = *pb;
     
    
   

    

     

    
    

     

          *pb = temp;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //快速排序优化算法：三数取中间
     
    
   

    

     

    
    

     

      int GetMidIndex(int* arr, int left, int right)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	
      int mid = (left + right) >> 
      1;
     
    
   

    

     

    
    

     
	
      if (arr[mid] > arr[left])
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		
      if (arr[left] > arr[right])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			
      return left;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
      else 
      if (arr[mid] > arr[right])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			
      return right;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
      else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			
      return mid;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      // arr[mid] < arr[left]
     
    
   

    

     

    
    

     
	
      else
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		
      if (arr[right] > arr[left])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			
      return left;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
      else 
      if (arr[mid] > arr[right])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			
      return mid;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
      else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			
      return right;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void QuickSort(int* arr, int left,int right)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	
      if (left >= right)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		
      return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      int index = 
      GetMidIndex(arr, left, right);
     
    
   

    

     

    
    

     
	
      int begin = left;
     
    
   

    

     

    
    

     
	
      int end = right;
     
    
   

    

     

    
    

     
	
      Swap(&arr[index], &arr[begin]);
     
    
   

    

     

    
    

     
	
      int pivot = begin;
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	
      int key = arr[begin];
     
    
   

    

     

    
    

     
	
      while (begin < end)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		
      //找小的
     
    
   

    

     

    
    

     
		
      while (begin < end && arr[end] >= key)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			--end;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		arr[pivot] = arr[end];
     
    
   

    

     

    
    

     

      		pivot = end;
     
    
   

    

     

    
    

     
		
      //找大的
     
    
   

    

     

    
    

     
		
      while (begin < end && arr[begin] <= key)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			++begin;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		arr[pivot] = arr[begin];
     
    
   

    

     

    
    

     

      		pivot = begin;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	pivot = begin;
     
    
   

    

     

    
    

     

      	arr[pivot] = key;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    
      QuickSort(arr, left, pivot - 
      1);
     
    
   

    

     

    
    

     
    
      QuickSort(arr, pivot + 
      1, right);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int findRepeatNumber(int* nums, int numsSize){
     
    
   

    

     

    
    

     
    
      assert(nums);
     
    
   

    

     

    
    

     
    
      int left = 
      0;
     
    
   

    

     

    
    

     
    
      int right = numsSize - 
      1;
     
    
   

    

     

    
    

     
    
      QuickSort(nums, left, right);
     
    
   

    

     

    
    

     
    
      int i = 
      0;
     
    
   

    

     

    
    

     
    
      for(i = 
      0; i < numsSize - 
      1; i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        
      if(nums[i] == nums[i + 
      1])
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            
      return nums[i];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return 
      -1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 

1.3 思路二

我们可以利用一个简单的哈希表：开辟一个同样大小的数组arr，并将数组arr初始化为0，然后遍历原来的数组nums，将nums数组的值对应到arr相应下标的位置，让他的值加一，如果再遍历过程中遇到arr的值大于1，则找到了该重复的数字。该解题方法的时间复杂度：O(N)，空间复杂度O(N)，以空间换时间。

  

   

    

     

    
    

     

      int findRepeatNumber(int* nums, int numsSize){
     
    
   

    

     

    
    

     
    
      int* arr = (
      int*)
      calloc(numsSize, 
      sizeof(
      int));
     
    
   

    

     

    
    

     
    
      int i = 
      0;
     
    
   

    

     

    
    

     
    
      for(i = 
      0; i < numsSize; i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              arr[nums[i]] += 
      1;
     
    
   

    

     

    
    

     
        
      if(arr[nums[i]] > 
      1)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            
      free(arr);
     
    
   

    

     

    
    

     

                  arr = 
      NULL;
     
    
   

    

     

    
    

     
            
      return nums[i];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      free(arr);
     
    
   

    

     

    
    

     

          arr = 
      NULL;
     
    
   

    

     

    
    

     
    
      return 
      -1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 

 1.4 思路三（最优解）

我们分析题目可以得到如下规律：数组大小是N，数值范围是N-1，如果说该数组没有重复的元素，那么数组中每一个下标都可以对应与其下标相同的数字，如果说有重复的数字，那么，会出现一个下标有多个与其下标相等的数字，或者出现没有与其下标相等的数字。

利用这一特性，我们可以遍历该数组，扫描到下标 i 时，首先比较这个数 m 与下标 i 是否相等，如果相等，继续扫描下一个元素。如果不相等，将m与下标为 m 的数进行比较，如果相等则找到一个重复的数字，如果不相等将 m 交换到下标为 m 的位置，对交换过来的数字继续重复上述判断即可，直到找到重复的数字。

解题的时间复杂度：O(N)，空间复杂度O(1)。

下面以一组例子来演示方便理解：

  

   

    

     

    
    

     

      void Swap(int* pa, int* pb)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    
      int temp = *pa;
     
    
   

    

     

    
    

     

          *pa = *pb;
     
    
   

    

     

    
    

     

          *pb = temp;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int findRepeatNumber(int* nums, int numsSize){
     
    
   

    

     

    
    

     
    
      int i=
      0;
     
    
   

    

     

    
    

     
    
      for(i = 
      0; i < numsSize; i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        
      while(nums[i] != i)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            
      if(nums[i] == nums[nums[i]])
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                
      return nums[i];
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
            
      Swap(&nums[i],&nums[nums[i]]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return 
      -1;
     
    
   

    

     

    
    

     

      }