调整数组顺序
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变
https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
奇数在前偶数在后 &&相对顺序可以改变的情况:
方法 1:遍历两次数组,第一次遍历遇到奇数的先放到数组中,第二次遍历遇到偶数的放到数组中
方法 2:头尾指针 , 头指针找偶数,尾指针找奇数,找到之后,二者交换
然后这里是奇数在前偶数在后 &&相对顺序不变的情况:
利用插入排序的思想:
k 前面的元素不需要再后移了,所以挪动的元素区间是(k,i],把前面的挪到后面去,从后往前挪
a[i]&1 == 0 ->偶数
a[i]&1 == 1 ->奇数
class Solution {public: void reOrderArray(vector<int> &array) { int k = 0;//标志应该存放奇数的位置 //遍历数组, //i位置遇到奇数:用临时遍历tmp保存当前位置的值 //就把[k,i-1)的元素往后移动,然后把tmp放到k位置下 //然后k++标志下一个应该存放奇数的位置 for(int i = 0;i<array.size();i++) { if(array[i] & 1) { //此时i位置为奇数,即i-1下标的元素为偶数 int tmp = array[i];//先保存当前位置的奇数 int j = i; //把(k,i-1]的元素往后移动 //k位置应该是我们放奇数的位置,所以该位置不需要往后移动 for(int j = i;j>k;j--) { array[j] = array[j-1]; } array[k++] = tmp; } } }};
复制代码
数组出现超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为 9 的数{1,2,3,2,2,2,5,4,2}.由于数字 2 在数组中出现了 5 次,超过数组长度的一半,因此输出 2.如果不存在则输出 0.
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
因为有可能并不存在出现次数超过一半的数字,所以我们最后找到之后还需要再次遍历数组判断是否符合要求
方法 1:定义 map <数字,次数>的映射关系,最后统计每个数字出现的次数
class Solution {public: int MoreThanHalfNum_Solution(vector<int> numbers) { unordered_map<int,int> map; int half = numbers.size()/2; for(int i = 0;i<numbers.size();i++) { auto it = map.find(numbers[i]);//在map中查找是否右numbers[i] //如果有,则自增,没有,则在map中插入该元素,首次出现 if(it!=map.end()) { map[numbers[i]]++; } else { map.insert(make_pair(numbers[i],1)) ; } //判断该元素的出现次数是否超过一半 if(map[numbers[i]]>half) { return numbers[i]; } } //找不到 return -1; }};
复制代码
方法 2:排序,出现次数最多的数字,一定在中间位置,然后再次遍历数组,检测中间出现的数字是否符合要求
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { sort(numbers.begin(),numbers.end());//对数组进行排序 int ans = numbers[numbers.size()/2];//中间位置 //判断是否符合条件 int sum =0; for(int i = 0;i<numbers.size();i++) { if(numbers[i] == ans) { sum++; } } //出现次数一定要>numbers.size()/2 不可以等于,因为超过一半 if(sum>numbers.size()/2) { return ans; } //并没有超过一半,即不存在超过一半的数字 return 0; }};
复制代码
方法 3:抵消的思想
目标条件:目标数据超过数组长度的一半.
那么对数组,我们同时去掉两个不同的数字,到最后剩下的一个数就是该数字.如果剩下两个,那么这两个也是一样的,就是结果）,将数组遍历一遍统计一下数字出现次数进行最终判断.
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int ans = 0; int count = 0;//ans出现的次数 for(int i =0;i<numbers.size();i++) { if(count == 0) { ans = numbers[i]; count=1;//注意要把count置为1 } else if(ans == numbers[i]) { count++; } else { count--; } } //判断是否符合条件 int sum =0; for(int i = 0;i<numbers.size();i++) { if(numbers[i] == ans) { sum++; } } //出现次数一定要>numbers.size()/2 不可以等于,因为超过一半 if(sum>numbers.size()/2) { return ans; } //并没有超过一半,即不存在超过一半的数字 return 0; }};
复制代码
评论