多数元素,自除数（力扣oj题）c语言解法

链接点这里

这也是我一开始用的方法，通过哈希表和一个记录次数的数组来完成(由于c语言没有哈希表，我只能通过数组来模拟，就导致了负数存不进去，所以我就将数向后移了500，就避免了负数的存在)，但是时间复杂度和空间复杂度都太大了。

int arr[100000]={0};//哈希表 
int brr[100000]={0};//记录次数 
#define aa 500//向前移动多少位 
int majorityElement(int* nums, int numsSize){
     int i;
     int max=0;
     for(i=0;i 
摩尔投票法 
 
 
这也是我从大神处学来的方法，
 仔细看题目，我们发现多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 所以就像打仗一样，多数元素中的各位与其他数的各位相持，留到最后的肯定是多数元素中的一位
 
 
代码的实现：
 
int majorityElement(int* nums, int numsSize){
     int k=0;
     int a=nums[0];//先假设多数元素为第一个元素
     int c=1; //a出现的次数
     for(k=1;k 
自除数 
题目 
 
 
 
限制条件： 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 
 
思路 
 
 
有了限制条件，我们就不能使用简单的暴力解法，一个个乘，而是要寻找一个时间复杂度低的算法
 
 
方法：左右累乘法 
直观图：
 
 
 
 
第一个循环先算左边的
 第二个循环再乘上右边的
 从而将时间复杂度降低到了o(n)
 思路清晰，让我们来写代码
 
 
代码： 
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    int* output=(int*)malloc(sizeof(int)*numsSize);
       int left=1;
       int right=1;
       int j=0;
       int i;
       for(i=0;i0)
         left=left*nums[i-1];
         output[i]=left;
       }
       for(i=numsSize-1;i>=0;i--)//先乘左边的
       {
         if(i