约翰有个整数数组。 约翰每次给数组中所有非零数都加上一个相等的数,可以加负数。 约翰希望尽快让数组变得全是0。
时间: 2024-05-31 19:12:52 浏览: 16
这是一个比较经典的问题,可以通过数学公式来解决。
我们先假设数组中有n个非零数,它们的和为S。如果我们每次让它们都减去x,那么数组的总和就会变成S - nx。
如果我们希望数组中的所有数都变成0,那么我们需要让S - nx = 0,解出x = S/n。
现在问题转化为,如何通过加上或减去一个数x,让数组中的所有非零数尽快变成0。
我们可以遍历数组,对于每个非零数a[i],我们计算出它需要加或减多少次x才能变成0,然后取所有次数的最大公约数,这个最大公约数就是我们每次需要加或减的数。
具体地,我们可以用一个变量diff来记录当前数组的总和与它应该有的总和之间的差值,即diff = S - nx。然后遍历数组,对于每个非零数a[i],我们可以计算出它需要加或减的次数为ceil(abs(a[i])/x),其中ceil表示向上取整。
最后,我们将所有次数的最大公约数作为每次需要加或减的数即可。
实际上,我们可以通过欧几里得算法来求最大公约数,这个算法的时间复杂度为O(logn)。因此,整个算法的时间复杂度就是O(nlogn)。
相关问题
给定一个整数数组 nums,将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序
。示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。
解法:
思路:双指针,一个指针指向下一个非零数应该存储的位置,一个指针遍历整个数组。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int index = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
for (int i = index; i < nums.size(); i++) {
nums[i] = 0;
}
}
};
C语言给定一个整数,对这个整数的一次转换是将这个整数这个整数的所有位数上非零数之积
对于给定的正整数N,可以按照以下步骤进行一次转换:
1. 将这个整数的所有位数上非零数相乘,得到积。
2. 如果积为0,则转换结果为0;否则,将积作为新的整数,重复步骤1,直到得到的积为一位数为止。
以下是C语言的代码实现:
```c
#include <stdio.h>
int main()
{
int n, product = 1;
scanf("%d", &n);
while (n != 0) {
int digit = n % 10;
if (digit != 0) {
product *= digit; }
n /= 10;
}
while (product >= 10) {
int new_product = 1;
while (product != 0) {
int digit = product % 10;
if (digit != 0) {
new_product *= digit;
}
product /= 10;
}
product = new_product;
}
printf("%d\n", product);
return 0;
}
```