数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
题解
参考以前写的博客:找出数组中出现次数超过一半的数
数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
题解 1
遍历数组,使用 Python 的关键字 in 判断该元素是否在其之后还出现过,如果是则直接返回。
|
|
题解 2
用布尔列表表示对应的值是否已经出现过 ,如果是则返回该值。
|
|
题解 3
由于数组长度为 n,且所有数字都在 0 到 n-1 的范围内,因此考虑利用数组下标。从下标 0 开始,对每个元素,若 numbers[i]
不等于 i
,则交换 numbers[i]
和 numbers[numbers[i]]
,直至 i
和 numbers[i]
相等继续循环,或 numbers[i]
和 numbers[numbers[i]]
相等即遇到重复元素返回 True。
|
|
调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
题解 1
一次遍历,判断每个数的奇偶性,然后使用两个列表来存储奇数和偶数,最后将两个列表合并。
|
|
题解 2
考虑用双指针。第一个指针初始化时指向数组的第一个数字,它只向后移动;第二个指针初始化时指向数组的最后一个数字,它指向前移动。如果第一个指针的数字是偶数,并且第二个指针指向的数字是奇数,就交换两个数字。
|
|
注意,题目要求保证奇数和奇数,偶数和偶数之间的相对位置不变。
同样采用双指针,第一个指针 left 从左向右遍历,找到第一个偶数,第二个指针 right 从 left+1 开始向后找,直到找到第一个奇数。然后,将 [left,…,right-1] 的元素整体后移一位,最后将找到的奇数放入 left 的位置,并且第一个指针继续向后进行下一次查找。
|
|