第一周練習(xí)——認(rèn)識(shí)復(fù)雜度和簡(jiǎn)單排序算法-創(chuàng)新互聯(lián)

前言：
👏作者簡(jiǎn)介：我是笑霸final，一名熱愛技術(shù)的在校學(xué)生。
📝個(gè)人主頁：個(gè)人主頁1 || 笑霸final的主頁2
📕系列專欄：《數(shù)據(jù)結(jié)構(gòu)與算法》
📧如果文章知識(shí)點(diǎn)有錯(cuò)誤的地方，請(qǐng)指正！和大家一起學(xué)習(xí)，一起進(jìn)步👀
🔥如果感覺博主的文章還不錯(cuò)的話，👍點(diǎn)贊👍 + 👀關(guān)注👀 + 🤏收藏🤏

創(chuàng)新互聯(lián)建站是工信部頒發(fā)資質(zhì)IDC服務(wù)器商，為用戶提供優(yōu)質(zhì)的成都天府聯(lián)通服務(wù)器托管服務(wù)

• 隨堂習(xí)題-排序（冒泡排序）
• 隨堂習(xí)題-排序（選擇排序）
• 隨堂習(xí)題-排序（插入排序）
• 隨堂習(xí)題-二分查找某數(shù)
• 隨堂習(xí)題-查找某個(gè)位置
• 隨堂習(xí)題-局部最小值問題
• 隨堂習(xí)題-一個(gè)數(shù)出現(xiàn)奇數(shù)次
• 隨堂習(xí)題-兩個(gè)數(shù)出現(xiàn)奇數(shù)次
• 隨堂習(xí)題-（遞歸）數(shù)組中的大值

給你一個(gè)n代表有n個(gè)數(shù)字，給出這n個(gè)數(shù)字，然后你需要使用冒泡排序?qū)⑦@些數(shù)字從小到大排好。

輸入描述:

第一行輸入一個(gè)n，代表有n個(gè)數(shù)字
第二行輸入n個(gè)數(shù)

輸出描述:

輸出排序好后的n個(gè)數(shù)

示例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;
}

給你一個(gè)n代表有n個(gè)數(shù)字，然后你需要使用選擇排序?qū)⑦@些數(shù)字從小到大排好。
輸入描述:

第一行輸入一個(gè)n，代表有n個(gè)數(shù)字
第二行輸入n個(gè)數(shù)

輸出描述:

輸出排序好后的n個(gè)數(shù)

示例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;
}

給你一個(gè)n代表有n個(gè)數(shù)字，然后你需要使用插入排序?qū)⑦@些數(shù)字從小到大排好。
輸入描述:

第一行輸入一個(gè)n，代表有n個(gè)數(shù)字
第二行輸入n個(gè)數(shù)

輸出描述:

輸出排序好后的n個(gè)數(shù)

示例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;
}

給你一個(gè)n代表有一個(gè)長(zhǎng)度為n的有序數(shù)組，然后給你一個(gè)k，你需要判斷這個(gè)k是否在數(shù)組里面，
如果存在就返回這個(gè)數(shù)從左往右第一次出現(xiàn)位置的下標(biāo)，如果不存在輸出-1。
輸入描述:

第一行輸入一個(gè)n，k，其中n代表有n個(gè)數(shù)字，k代表你需要查找的元素
第二行輸入n個(gè)數(shù)

輸出描述:

如果在數(shù)組里面找到了k，輸出k所在的下標(biāo)（注：如果數(shù)組中k出現(xiàn)了多次，請(qǐng)輸出最小的下標(biāo)?。?，如果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]//交換兩個(gè)數(shù)
                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]//交換兩個(gè)數(shù)
                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  所以局部最小值應(yīng)該在右邊
            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];
     //如果所有的數(shù)異或運(yùn)算 最后的值一定是出現(xiàn)奇數(shù)次的兩個(gè)數(shù)的異或 并且一定不為0 
     //例如1111 和 1000 他們異或 為 0111
     int eor=0;
     
     for(int i=0;i //把和rightOne位置同為1的數(shù)異或 那么得到的數(shù)就是其中的一個(gè)答案
        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;
}