第一周练习——认识复杂度和简单排序算法-创新互联

前言：
👏作者简介：我是笑霸final，一名热爱技术的在校学生。
📝个人主页：个人主页1 || 笑霸final的主页2
📕系列专栏：《数据结构与算法》
📧如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
🔥如果感觉博主的文章还不错的话，👍点赞👍 + 👀关注👀 + 🤏收藏🤏

创新互联建站是工信部颁发资质IDC服务器商，为用户提供优质的成都天府联通服务器托管服务

• 随堂习题-排序（冒泡排序）
• 随堂习题-排序（选择排序）
• 随堂习题-排序（插入排序）
• 随堂习题-二分查找某数
• 随堂习题-查找某个位置
• 随堂习题-局部最小值问题
• 随堂习题-一个数出现奇数次
• 随堂习题-两个数出现奇数次
• 随堂习题-（递归）数组中的大值

给你一个n代表有n个数字，给出这n个数字，然后你需要使用冒泡排序将这些数字从小到大排好。

输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1
输入:

4
4 3 2 1

输出:

1 2 3 4

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;icin >>nums[i];
    }
    //冒泡
    for(int i=n-1;i>0;i--){for(int j=0;jif(nums[j]>nums[j+1]){nums[j]  =nums[j] ^ nums[j+1];
                nums[j+1]=nums[j] ^ nums[j+1];
                nums[j]  =nums[j] ^ nums[j+1];
            }
        }
    }
    //输出
     for(int i=0;icout<< nums[i]<<" ";
    }
    return 0;
}

给你一个n代表有n个数字，然后你需要使用选择排序将这些数字从小到大排好。
输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1
输入:

4
4 3 2 1

输出:

1 2 3 4

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;icin >>nums[i];
    }
    //选择排序
    
    for(int i=0;iint vauleMinIndex=i;
        for(int j=i+1;jif(nums[vauleMinIndex]>=nums[j]){vauleMinIndex=j;
            }
        }
        swap(nums[i], nums[vauleMinIndex]);
    }
    //输出
     for(int i=0;icout<< nums[i]<<" ";
    }
    return 0;
}

给你一个n代表有n个数字，然后你需要使用插入排序将这些数字从小到大排好。
输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1
输入:

4
4 3 2 1

输出:

1 2 3 4

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;icin >>nums[i];
    }
    //插入排序
    for(int i=0;ifor(int j=1;jif(nums[j]swap(nums[j],nums[j-1]);
            }
        }
    }
    //输出
     for(int i=0;icout<< nums[i]<<" ";
    }
    return 0;
}

给你一个n代表有一个长度为n的有序数组，然后给你一个k，你需要判断这个k是否在数组里面，
如果存在就返回这个数从左往右第一次出现位置的下标，如果不存在输出-1。
输入描述:

第一行输入一个n，k，其中n代表有n个数字，k代表你需要查找的元素
第二行输入n个数

输出描述:

如果在数组里面找到了k，输出k所在的下标（注：如果数组中k出现了多次，请输出最小的下标！），如果k不在，就输出-1

示例1
输入:

7 0
0 1 2 3 4 5 6

输出:

0

代码

#include#includeusing namespace std;
int main(){int n=0,k=-1,tep=-1;
    cin>>n;cin>>k;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;i>nums[i];
    
    for(int i=0;i//插入排序
        for(int j=1;jif(nums[j]//交换两个数
                nums[j]  = nums[j] ^ nums[j-1];
                nums[j-1]= nums[j] ^ nums[j-1];
                nums[j]  = nums[j] ^ nums[j-1];
            }
        }
    }
   //二分查找
    int l=0,r=n-1;
    while(l<= r){int mid = l + ((r -l ) >>1);
        if(nums[mid]<  k) l=mid+1;
        if(nums[mid] >k) r=mid-1;
        if(nums[mid] == k){//查重
            if(nums[mid-1]< nums[mid]){tep = mid;
            }
             r= mid-1;
        }
    }
    cout<

#include#includeusing namespace std;
int main(){int n=0,k=-1,tep=-1;
    cin>>n;cin>>k;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;i>nums[i];
    
    for(int i=0;i//插入排序
        for(int j=1;jif(nums[j]//交换两个数
                nums[j]  = nums[j] ^ nums[j-1];
                nums[j-1]= nums[j] ^ nums[j-1];
                nums[j]  = nums[j] ^ nums[j-1];
            }
        }
    }
   //二分查找
    int l=0,r=n-1;
    while(l<= r){int mid = l + ((r -l ) >>1);
        if(nums[mid]<  k) l=mid+1;
        if(nums[mid] >k){r=mid-1;
            tep=mid;
        } 
        if(nums[mid] == k){tep=mid;
            //查重
            if(nums[mid-1] >nums[mid]){tep = mid;
            }
             r= mid-1;
        }
    }
    cout<

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
     if(n<=0) { cout<< -1<< endl;
        return 0;
    }
    vectornums(n);
    for(int i=0;i>nums[i];
   
    //开头局部最小
   if(n==1 || nums[0]< nums[1]){cout<< 0<< endl;
        return 0;
   }
    if(n==2 && nums[0]>nums[1]){cout<< 1<< endl;
        return 0;
    }
    //末尾局部最小
    if (nums[n-1]< nums[n-2]){cout<< n - 1<< endl;
        return 0;
    }
   //二分查找
    int l=0,r=n-1;
    while(l<= r){int mid = l + ((r -l ) >>1);
        if(nums[mid]< nums[mid-1] && nums[mid]cout<< mid<< endl;
            return 0;
        }
        else if( nums[mid]//说明mid+1也小于于mid  所以局部最小值应该在右边
            l=mid+1;
        }
        else  r=mid-1;
    }
    cout<<-1;
    return 0;
}

#includeusing namespace std;
 int main(){ int n=0;
     cin>>n;
     if(n<=0){ cout<<-1;
         return 0;
     }
     vectorarr(n);
     for(int i=0;i>arr[i];
     
     int x=0;
     for(int i=0;i x=x^arr[i];
     }
     cout<< x<

#includeusing namespace std;
 int main(){ int n=0;
     cin>>n;
     if(n<=0){ cout<<-1;
         return 0;
     }
     vectorarr(n);
     for(int i=0;i>arr[i];
     //如果所有的数异或运算 最后的值一定是出现奇数次的两个数的异或 并且一定不为0 
     //例如1111 和 1000 他们异或 为 0111
     int eor=0;
     
     for(int i=0;i //把和rightOne位置同为1的数异或 那么得到的数就是其中的一个答案
        if( (rightOne & arr[i]) != 0){onlyOne ^= arr[i];
        }
     }
    int y= eor^onlyOne;
        if(onlyOne  cout<< onlyOne<<" "<< y;
        }else{ cout<< y<<" "<< onlyOne;
        }
     return 0;
 }

#include#includeusing namespace std;

//递归
int myMax(int arr[],int l,int r){if(l==r){return arr[l];
    }
    int mid=l+((r-l)>>1);
    int leftmax=myMax(arr,l,mid);
    int rightmax=myMax(arr,mid+1,r);
    return leftmax >rightmax ? leftmax : rightmax;
}

int main(){int n;
    cin>>n ;
    if(n<=0) return 0;
     int *arr = new int[n];
    //vectorarr(n);
    for(int i = 0 ;i< n ; i++){cin>>arr[i];
    }
    cout<< myMax(arr,0,n-1);
    return 0;
}