1. 奇数在左偶数在右
给定一个数列A，试将其变为奇数在左偶数在右的形式。例如A=[12,8,7,5,6,11]，则变换后的A'=[11,5,7,8,6,12]
只需要先奇数后偶数即可，不需要排序。
思路: 题目要求奇数在前，偶数在后，那么我选择采取快排中的一个经典算法双指针的方法.
- 左指针寻找偶数值，右指针寻找奇数值，当符合交换条件时，进行两数交换；
- 否则指针继续左右运动，寻找符合条件的奇偶值。
- 当两指针相遇时，结束循环。
代码如下:
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int main()
{
int a[] = { 12,8,7,5,6,11 };
//左右指针初始化
int left = 0;
int right = sizeof(a)/sizeof(int)-1;
while (left < right)
{
while (left<right&&a[left] % 2 != 0)//左指针对应是奇数,符合题意指针继续往下走
{
left++;
}
while (left<right&&a[right] % 2 == 0)//右指针对应是偶数,符合题意指针继续往下走
{
right--;
}
swap(&a[left], &a[right]);//左指针的偶数与右指针的奇数交换
}
for (int i = 0; i < 6; i++)
{
printf("%d ", a[i]);
}
return 0;
}
2. 最快效率求出乱序数组中第k小的数
以尽量高的效率求出一个乱序数组中按数值顺序的第k 的元素值
思路:这里很容易想到直接排序然后顺序查找，可以使用效率较高的快排，但是它的时间复杂度是O(nlgn)，我们这里可以用一种简便的方法，不一定需要排序，使用快速排序中双向分区的扫描方法，这里使用的是优化过后的三点中值法，具体思想一样，只是主元的取法不一样。然后扫描出主元下标，然后根据主元的值将数组划分成一半大，一半小。然后再根据主元下标与k进行比较，如果相等，说明主元就是我们要找的数，如果大于k，说明k所代表的值在小的那边，继续向小的那部分递归，如果小于k，说明k代表的值在大的那边，继续向大的那部分递归。这样即可得出正确答案。这种方法的时间复杂度为**O(n)**，因为每次递归都相当于舍弃掉了差不多一半的数。
代码如下:
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int getmidindex(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
else {
if (a[left] < a[right])
return left;
else if (a[mid] > a[right])
return mid;
else
return right;
}
}
int partion(int* a, int left, int right)
{
int mini = getmidindex(a, left, right);
swap(&a[mini], &a[left]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
right--;
while (left < right && a[left] <= a[keyi])
left++;
swap(&a[left], &a[right]);
}
swap(&a[left], &a[keyi]);
return left;
}
int quicksort(int* a, int left, int right,int k)
{//left开始的下标,right结束的下标,k求第k个元素
int keyi = partion(a, left, right);//主元的下标
int qk = keyi - left + 1; // 主元是第几个元素
if (qk == k) {
return a[keyi];
}
else if (qk > k) {
return quicksort(a, left,keyi - 1, k);
}
else {
return quicksort(a, keyi + 1, right, k-qk);
}
}
int main()
{
int a[] = { 12,8,7,5,6,11 };
int b=quicksort(a, 0,5,6);
printf("%d", b);
return 0;
}
3. 数组中有一个数字出现次数超过数组长度一半
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
思路:本题思路比较多,可以用哈希表,摩尔投票,分治,比特操作法等等来做,本题我提供哈希和分治的种做法.
哈希表: 使用unordered_map实现哈希表映射， 它是C++的STL中的的hash表实现函数
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> unmap;
for(auto num:nums)
{
unmap[num]++;
if(unmap[num]>nums.size()/2)
{
return num;
}
}
return 0;
}
};
分治:我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数.
代码:
class Solution {
int count_in_range(vector<int>& nums, int target, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; ++i)
if (nums[i] == target)
++count;
return count;
}
int majority_element_rec(vector<int>& nums, int lo, int hi) {
if (lo == hi)
return nums[lo];
int mid = (lo + hi) / 2;
int left_majority = majority_element_rec(nums, lo, mid);
int right_majority = majority_element_rec(nums, mid + 1, hi);
if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
return left_majority;
if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
return right_majority;
return -1;
}
public:
int majorityElement(vector<int>& nums) {
return majority_element_rec(nums, 0, nums.size() - 1);
}
};
4. 合并两个有序数组
思路:可以将先将nums2数组放到nums1后面然后再用sort进行排序即可,这个方法我就不写了，我主要是帮助大家练习前面排序算法学到的思想来做这道题.也可以用快排里面的双指针方法来做这道题
代码:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int end1=m-1,end2=n-1;
int end=m+n-1;
while(end1>=0&&end2>=0){
if(nums1[end1]>nums2[end2]){
nums1[end--]=nums1[end1--];
}
else{
nums1[end--]=nums2[end2--];
}
}
while(end2>=0){
nums1[end--]=nums2[end2--];
}
}
5. 数组中的逆序对
思路:借鉴力扣的一位大佬的思路讲解,大家可以去看看讲解的超级详细.
代码:
class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<int> tmp(nums.size());
return mergeSort(0, nums.size() - 1, nums, tmp);
}
private:
int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) {
// 终止条件
if (l >= r) return 0;
// 递归划分
int m = (l + r) / 2;
int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);
// 合并阶段
int i = l, j = m + 1;
for (int k = l; k <= r; k++)
tmp[k] = nums[k];
for (int k = l; k <= r; k++) {
if (i == m + 1)
nums[k] = tmp[j++];
else if (j == r + 1 || tmp[i] <= tmp[j])
nums[k] = tmp[i++];
else {
nums[k] = tmp[j++];
res += m - i + 1; // 统计逆序对
}
}
return res;
}
};
6. 排序数组中两个数字之和
思路:一看这道题目就很容易想到循环暴力破解，时间复杂度为n²。这样肯定不太理想，所以得换解法，题目已经说了是已排序数组，那么就可以用二分查找，先给定首指针元素，然后再用K去减去首指针元素，再去二分查找剩下一个元素在不在数组。然后首指针右移，这样就能全部找出来了，这种解法的时间复杂度为NlgN。这道题还有另一种解法，我们可以设置左右指针同时扫描，扫描出两个数之和等于K，那么这两个数就是要找的那两个数。
二分查找大家伙可以实现下,因为要熟悉前面学习地知识我就只写左右指针方法了
代码:
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int low = 0, high = numbers.size()-1;
while(low < high){
if(numbers[low] + numbers[high] == target){
return {low, high};
}
if(numbers[low] + numbers[high] < target){
low++;
}
if(numbers[low] + numbers[high] > target)
high--;
}
return {};
}
};
7. 解决员工年龄问题
思路:可以运用结构体和c++自带的sort做这道题,或者用哈希表也可以做大家可以去试一下,不过这里为了呼应前文,提供另一种做法,首先我们观察下年龄的范围1到99不算大,我们可以采用计数排序来做这道题.
代码:
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] arr = new int[n];
for(int i =0 ;i<n;i++){
arr[i] = input.nextInt();
}
System.out.println(Arrays.toString(arr));
int[] tempArr = new int[100];
for(int i =0;i<n;i++){
tempArr[arr[i]]++;
}
for(int i =0,index = 0;i<tempArr.length;i++){
while(tempArr[i]!=0){
arr[index++] = i;
tempArr[i]--;
}
}
System.out.println(Arrays.toString(arr));
}
}
8. 拓展:把数组排成最小的数
思路:这道题我采用的是把数组转换成字符串然后使用C++的内置函数sort进行排序,sort大家不明白的可以去了解一下,还是挺方便的,后面我也会专门介绍
代码
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
string res;
for(auto num:nums)
strs.push_back(to_string(num));
sort(strs.begin(),strs.end(),compare);
for(auto str:strs)
res+=str;
return res;
}
private:
static bool compare(const string &a,const string &b)
{
return a+b<b+a;
}
};
版权归原作者 skeet follower 所有， 如有侵权，请联系我们删除。