当前位置: article > 正文

数组 + 二分 --coding_任意三个数按照从大到小输出这三个数字c++

作者：IT小白 | 2024-02-29 05:53:53

踩

任意三个数按照从大到小输出这三个数字c++

1、找一个数组中出现奇数次的那个数，要求时间复杂度O(N)，空间复杂度O(1)

5.1、数组中找出多组三个数abc，a+b+c=0

9、找出来数组中每个元素后边第一个比它大的值，要求复杂度为O(n)

10、找出数组前K大的数（Top K）

11、寻找无序数组中的第K小 / 第K大的数

12、给两个有序数组，求第K大的数

13、寻找两个有序数组的中位数

14、前 K 高频元素

15、查找重复数（LeetCode287）

16、计算任意（N-1）个数的组合中乘积最大的一组

17、滑动窗口的最大值

18、数组分成m段求各段和的最大值最小是多少

19、丑数

20、二分查找:

21、有序数组，给定k，找到 k的最后一次出现的索引

22、给定两个队列，实现一个栈的功能；

23、岛屿数量问题

23、二维数值中查找

24、1-N的自然数中，少了一个，找出这个数

扩展：如果删除两个元素呢，找到这两个元素

1、找一个数组中出现奇数次的那个数，要求时间复杂度O(N)，空间复杂度O(1)

延伸：除了一个数出现了一次，其他数字出现了两次，找出这个出现了一次的数（异或）

方法取巧，0 跟数组里的数异或

参考：检测一个数组里面出现次数为奇数的数字_JULIUS_0的博客-CSDN博客

方法：异或运算为基础，偶数个一样的数异或为0， 0 和任何数异或，都是这个数本身，异或符合交换律，所以只需要把所有数组中所有数字异或一次就可以了


int findIt(int[] A) {
    int xor = 0;
    for (int i = 0; i < A.length; i++) {
      xor = xor^A[i];
    }
    return xor;
}

2、数组逆序输出


void reversech(int[] num)
{
	int len = num.length()
  //把第一个与最后一个交换;
	for (int i=0; i< len/2; ++i)
	{
		int temp = ch[i];
		num[i] = ch[len-1-i];
		num[len-1-i] = temp;
	}
}

3、查找两个数组中的相同元素

假设，这两个数组已经排好序（升序），那么只需要遍历一次即可。

首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字


void findcommon2(int a[], int size1, int b[], int size2)
{
     int i=0,j=0;
     vector<int> vec；
 
     while(i<size1 && j<size2) 
    {
          if(a[i]==b[j]) 
         {
            vec.push_back(a[i]);
            i++;
            j++;
          }
          if(a[i]>b[j])
               j++;
 
          if(a[i]<b[j])
               i++;
     }
}

4、输入一个数组，要求奇数在左，偶数在右

一左一右两个指针，遇到正负数不符合的交换位置


void fun(int[] arr){
    int left = 0,right = arr.length-1;
    while(left < right){
        while(arr[left] % 2 == 1  && left < right){
            left++;
        }
        while(arr[right] % 2 == 0 && left < right){
            right--;
        }
        if(left < right){
            swap(arr,left,right);
        }
    }
}

5、正负数交替

一个数组，数组中有正数和负数，重新排列这个数组，使得原始数组中的正负数交替排列，且保证各自的相对顺序不变。


void fun1(int[] arry) {
	
	for(int i=0; i <= arry.length; i++) 
	{
		
		if(i % 2 == 0 && arry[i] > 0)  //判断所在位置应该是正数
			continue;
		else 
		{   
            // 不是正数，则查找第一个正数，交换
			for(int j=i+1; j<arry.length; j++) 
			{
				if(arry[j] > 0) {
					swap(arry[i], arry[j]);
					break;
				}												
			}
		}
		
		if(i % 2 == 1 && arry[i] < 0)  //判断所在位置应该是负数
			continue;
		else 
		{
			for(int j=i+1; j<arry.length; j++) 
			{
				if(arry[j] < 0) {
					swap(arry[i], arry[j]);
					break;
				}				
			}
		}
		
	}
}

5.1、数组中找出多组三个数abc，a+b+c=0

一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0。请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。


public List<List<Integer>> threeSum(int[] nums) {
 
	nums = sort(nums) //先排序
	int n = nums.length;
	
	List<List<Integer>> res = new LinkedList<>();
	
	
	for (int i = 0; i < n - 2; i++) {
	    if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
		
		// 去掉重复情况，如果两个数字相同，我们直接跳到下一个循环。
		if (i > 0 && nums[i] == nums[i - 1]) {
			continue；
		};
		int left = i + 1;    // 左边的第一个数
		int right = n - 1;   // 右边的最后一个数字
		
		// num[i] 是第一个数，则我们要动态寻找的另外两个数的和应该是 nums[left] + nums[right] = -nums[i] 
		int target = -nums[i] 
		
		while (left < right) {
			
		   if (nums[left] + nums[right] > -nums[i])
				right--;    // 两数之和太大，右指针左移
			else if (nums[left] + nums[right] < -nums[i])
				left++;     // 两数之和太小，左指针右移
			else if (nums[left] + nums[right] == -nums[i])
			{
				// 找到一个和为零的三元组，添加到结果中，左右指针内缩，继续寻找
				res.push_back(vector<int>{nums[i], nums[left], nums[right]});
 
				 // 现在要增加 left，减小 right，但是不能重复(第二个数和第三个数也不重复选取)，
				 // 比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
				
				left++;  // 先进行加减操作
				right--;
	
		        // 然后去重， 上面已经对index做了加减操作，所以left 要跟left-1比较， right 要跟 right+1 比较
				while (left < right && nums[left] == nums[left-1])  left++;
				while (left < right && nums[right] == nums[right+1])    right--;
			}
		}
	}
	return res;
}

LeetCode：

解法1：力扣

解法2：力扣

15. 三数之和 - 简书

5.2、判断是否为平方数之和

通常解法：双指针 leetcode笔记--633.判断给定的数是否为两个数平方的和_Eunice_Qiu的博客-CSDN博客

归纳法和动态规划解法：LintCode 697: 判断是否为平方数之和 -- O(n) 解法_Andrew Yang的博客-CSDN博客

6、数组中出现最多的元素

遍历数组的所有元素一次：O（n）

对于访问的每个元素，检查它的key是否已存在于HashMap

如果它没有（第一次看到这个元素），那么把它添加到你的HashMap中[key：this element，value：1]。

如果确实存在，则将与该键对应的值递增 1

完成构建HashMap之后，遍历map并找到具有最高次数的元素 - 这是出现次数最多的元素。

部分代码解决方案，让你了解如何使用HashMap：


int find(int[] arry) {
    HashMap hm = new HashMap();
    for (int i = 0; i < array.length; i++)
     {
 
        Double key = new Double(array[i]);
        if ( hm.containsKey(key) )
         {
            value = hm.get(key);
            hm.put(key, value + 1);
          } 
        else 
        {
            hm.put(key, 1);
        }
    }
}

7、查找众数

给一数组，找出数组中的众数，众数就是出现的次数超过一半的数

假设数组不为空，且众数一定存在

方法1：hashmap

通过遍历数组，将数组每个数都通过hashmap来统计其出现的个数，如果某个数个数超过一半，则为众数。

时间空间复杂度均为O(n)

方法2：Moore Voting Algorithm

众数存在的情况下，每次扔掉两个不同的数，众数不变，最终剩下的数一定是众数。

扔掉一个众数和一个非众数，众数不变
扔掉两个非众数，众数不变

时间复杂度O(n)，空间复杂度O(1)

摩尔投票算法：

先假设第一个元素为众数，计数器置为1，遍历数组，当遇到相同的元素时，计数器加1，否则减1，任何计算器为0的时候，就假设下一个元素为众数，计数器再置为1。循环结束时，返回我们假设的众数，即要求的众数。前提是存在众数即个数超过一半的数字

LeetCode：力扣


// hash_map method
int majorityElement1(vector<int> &num) {
	int n =num.size();
	if(n==1) return num[0];
	map<int,int> m;
	for(vector<int>::iterator it=num.begin();it!=num.end();it++){
		m[*it]+=1;
		if(m[*it] > floor(n/2))
			return *it;
	}
	return -1;
}
 
int majorityElement(int[] nums) {
	int len = nums.length;
	int count = 0;
 
	int value;  // 众数
	
	for(int i = 0; i < len; i++){
		// 上一个循环 count 为0，则当次的 nums 设置为 众数 value，同时 count 设置为 1
		if(count == 0) {
			value = nums[i]
			count = 1；
		} 
		else {
		    // 两个值不相等，则扔掉这两个数, 相等则 计数加1
			if (value == nums[i]){
				count++;
			} else{
				count--;
			}
		}
	}
	return value;
}

8、数组元素的全排列

考察：回溯法

LeetCode：力扣

相似问题：

1、电话号码的字母组合：力扣

2、组合总和:LeetCode：力扣


 
void persort(int[] arr,int start)
{
   //start代表从arr中的第几个数开始
        //当start==arr.length-1时，说明子序列的长度为1，就不用再往下分子序列了
		if(start==arr.length-1)
        {
			for(int i=0 ;i<=m ;i++)
		       cout<<list[i];
		       cout<<endl; 
		}
		for(int i=start;i<arr.length;i++)
         {
            //start代表的是每一个子序列的第一个位置，我们每一层递归的任务都只有一个：
            //枚举该层子序列第一个位置可以取的值
			int temp=arr[start];
			arr[start]=arr[i];
			arr[i]=temp;
			
            //该层递归的子序列第一个位置已经确定了，所以又可以往下再分
			persort(arr,start+1);
 
            //把第该层子序列第一个位置的值换成另外一个值，所以要交换回来
			temp=arr[start];
			arr[start]=arr[i];
			arr[i]=temp;
		 }
}

2、全排列（递归算法）_MsStrbig的博客-CSDN博客_全排列

9、找出来数组中每个元素后边第一个比它大的值，要求复杂度为O(n)

如数组A=[6,8,9,2,3,5,6] 输出[8,9,-1,3,5,6,-1]

思路：

我们用栈来保存未找到右边第一个比它大的元素的索引（后面要用索引来给res数组赋值）步骤如下：

对于当前遍历的第i个元素有：

1. 栈为空，则当前索引i入栈，同时说明前面的元素都找到了右边比它大的元素
2. 栈不为空，如果栈顶索引元素大于等于当前元素，则将当前索引i入栈；（目的是为了保持栈从栈底到栈顶非升序）
3. 栈不为空，当前元素大于栈顶索引元素，则栈顶索引元素对应的第一个比它大的元素就是当前元素，保存当前元素；同时为了保证栈底到栈顶非升序需要将栈顶元素弹出，

4. 循环判断1、2、3条件，直到满足1、2条件。
5. 输入遍历完，栈中还剩余的元素则是不能找见之后比他大的元素。

遍历完所有元素，如果栈不为空，说明栈中保存的全是未找到右边第一个比它大的数组索引，我们依次将这些栈元素出栈，并赋值result[stack.pop()] = -1即可。

问题分析：利用单调栈，从左至右依次压入数据的索引（若直接压数，则还需要一个数组保存栈中元素所对应的数组位置），如果当前元素小于等于栈顶的索引所对应的数组的值，入栈当前索引，否则将栈顶索引出栈，并在栈顶索引所对应的res数组中记录下当前的值。到最后再检查栈中剩余元素，代表剩余元素右边没有比它大的值，在res对应位置赋值为-1。


void findNearestMax(int *arr,int n,int *res) {
    int i = 0;
    stack<int> s; // 存放id
    //开辟一个新空间，存放结果
    int *res= new int[arr.length];    
 
    while (i < n) {
 
        // 条件 1 和 条件2 的判断
		if (s.empty() || arr[s.top()] >= arr[i])
			s.push(i++);
		else
		{
            //这个判断里面，当找到的 arr[i] > arr[s.top()],则将栈s.top出栈，
            // 同时将 res中 索引为 s.top() 的元素值改成，arr[i],
            //但是 i 没有改变，继续判断该元素arr[i]是否还大于栈里面的其他元素
            //直到找不满足上述条件则将该元素id入栈
            
			res[s.top()] = nums[i];
			s.pop();
		}    
    }
    // 剩下的则是没有找到比该元素大的数
    while (!s.empty()) {
        res[s.top()] = -1;
        s.pop();
    }

10、找出数组前K大的数（Top K）

剑指Offer 29、最小的K个数：【剑指Offer】29、最小的K个数 - gzshan - 博客园

LeetCode：力扣


 vector<int> quickSort(vector<int>& arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }

11、寻找无序数组中的第K小 / 第K大的数

- 数组求第k小数字的下标

思路解析（代码有问题）

1、最暴力的思想，直接排序，然后索引第k个数据，最优的排序算法时间复杂度为O(nlog(n)),但是随着n的变大，复杂度增长

2、借助快速排序的思想

　　快速排序的思想是通过一趟排序将要排序的list分为2部分，左边小，右边大。然后递归排序左右。我们可以在每一趟排序后，比较基准元素的索引和K的大小，若k大于基准元素的索引，则要寻找的k大数字就在基准元素的右边，否则左边。直到找到基准元素的索引等于K。时间复杂度 O(n)

3、堆排序，查看LeetCode中得讲解

求第k大相当于求第n-k+1小，n为数组长度。或者快排时候左边是大数右边是小数。下面展示第K小


int quick_sort( int[] arry, int left, int right ) {
	
    int value = arry[left]; #拿出第一个数当作基准数value
    int low = left;      #low来标记左侧从基准数始找比value大的数的位置
    int high = right;    #high来标记右侧right向左找比value小的数的位置
 
    # 我们要进行循环，只要low和high没有碰头就一直进行,当low==high说明碰头了
    while (low < high) {
	
        while(low < high && arry[high] > value ) {
		    high--;
		}
        while(low < high && arry[low] <= value ) {
			low--;
		}
		swap(arry[low], arry[high])；
	}
    
    # 基准元素归位
    arry[left] = arry[low]；
    #当这个while跳出来之后相当于low==high碰头了，我们把index的数值放在这个空位
    arry[low] = value；
	
    #这个时候index左侧看的数都比index小，index右侧的数都比index大
    return low
}
 
int find_k(int[] arry, int k) {
 
    int n = len(arry);
    int left = 0;
    int right = n-1;
    int index = partition(arry,left,right);
    while (index != k) {
		if (index>k) {
			right = index-1;
			index = quick_sort(arry,left,right);
		}
		else {
			left = index+1;
			index = quick_sort(arry,left,right);
		}
	}
 
    return arry[k]
}

堆排序：

LeetCode：力扣

12、给两个有序数组，求第K大的数

分析：

解法一：游标计数

题目只要求第k大的数，没必要花力气将数组全部再排序，可以定义两个游标分别指向两个有序数组，按序移动，并用count计数，当count等于k时，返回两个游标指向的数中最小的那一个

时间复杂度O(m+n),空间复杂度O(m+n)


int find_Kth( int* array1, int len1, int* array2, int len2, int K )
{
    if(!array1||!array2||len1==0||len2==0)
        return -1;
    int i = 0;
    int j = 0;
    int count = 0;
 
    while( count<K-1 )
    {
        if( array1[i]<=array2[j] )
            i++;
        else
            j++;
        count++;
    }
    return array1[i]>=array2[j]?array2[j]:array1[i];
}

二分法：

有没有更好的方案呢？我们可以考虑从 k 入手。如果我们每次都能够删除一个一定在第 k 大元
素之前的元素，那么我们需要进行 k 次。但是如果每次我们都删除一半呢？由于 A 和 B 都是有序
的，我们应该充分利用这里面的信息，类似于二分查找，也是充分利用了“有序” 。
假设 A 和 B 的元素个数都大于 k/2，我们将 A 的第 k/2 个元素（即 A[k/2-1]）和 B 的第 k/2
个元素（即 B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设 k 为偶数，所得到的结
论对于 k 是奇数也是成立的）：
• A[k/2-1] == B[k/2-1]
• A[k/2-1] > B[k/2-1]
• A[k/2-1] < B[k/2-1]
如果 A[k/2-1] < B[k/2-1]，意味着 A[0] 到 A[k/2-1] 的 k/2 个元素肯定在 A ∪ B 的 top k 元素的范围
内，换句话说，A[k/2-1]不可能大于 A ∪ B 的第 k 大元素
因此，我们可以放心的删除 A 数组的这 k/2 个元素。同理，当 A[k/2-1] > B[k/2-1] 时，可
以删除 B 数组的 k/2 个元素。
当 A[k/2-1] == B[k/2-1] 时，说明找到了第 k 大的元素，直接返回 A[k/2-1] 或 B[k/2-1]
即可。
因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？
• 当 A 或 B 是空时，直接返回 B[k-1] 或 A[k-1]；
• 当 k=1 是，返回 min(A[0], B[0])；
• 当 A[k/2-1] == B[k/2-1] 时，返回 A[k/2-1] 或 B[k/2-1]

比较简单的情况：假设 A 和 B 的元素个数都大于 k。则不存在 A、B为空的情况：


def Binary_find_Kth(self, arrayA,arrayB,k):
	m = len(arrayA)
	n = len(arrayB)
	# 保持让arrayA的长度最小
	if m > n:
        return self.Binary_find_Kth(arrayB,arrayA,k)
	if m == 0:
        return arrayB[k-1]
	if k == 1 :
        return min(arrayA[0],arraybB[0])
	
	# 将k分成两部分，一部分在arrayA上，一部分在arrayB上
	# 保证 k1 + k1 = k
	k1 = k // 2
	k2 = k - k1
 
	if arrayA[k1-1] > arrayB[k2-1]:
		return Binary_find_Kth(arrayA,arrayB[k2:],k-k2)
	# 由于题目说了没有交集，这里不考虑相等情况
	elif arrayA[k1-1] < arrayB[k2-1]:
		return Binary_find_Kth(arrayA[k1:],arrayB,k-k1)	
	else arrayA[k1-1] == arrayB[k2-1]:
		return arrayA[k1-1]

2、全面考虑数组长度和 k 的大小


 
/*在两个升序排序的数组中找到第k大的元素*/
int Binary_find_Kth(int* array1, int len1, int* array2,int len2, int k)
{	
	if( k < 0 )
	{
		cout<<"Invalid k = "<<k<<endl;
		return -1;
	}
	// 在这里始终保证 len1 <= len2
	if( len1 > len2 )
		return Binary_find_Kth(array2,len2, array1,len1, k);
	if( len1 == 0 )
		return array2[k-1];
	if( k == 1)
		return ((array1[0]>= array2[0]) ? array2[0] : array1[0]);
 
	// 不一定每个数组都有k/2个元素,上面保证了， len1 < len2
	int k1 = min(k/2, len1)
	int k2 = k - k1; 
	
	/**
	说明array2的k2-1前部分一定在第k大元素之前，因此：
	1）将k2-1这部分全跳过:更新数组首位地址索引，同时更新数组长度；
	2）将这k2元素纳入已找到的第k大元素范围内，更新k值：k-k2
    **/
	
	if( array1[k1-1] > array2[k2-1] )
	{
		return Binary_find_Kth(array1, len1, &array2[k2], len2-k2, k-k2);
	}
 
    /**
        说明array1的k1-1前部分一定在第k大元素之前，因此：
        1）将k1-1这部分全跳过:更新数组首位地址索引，同时更新数组长度；
        2）将这k1元素纳入已找到的第k大元素范围内，更新k值：k-k1
    **/	
	
	else if( array1[k1-1] < array2[k2-1] )
	{
		return Binary_find_Kth(&array1[k1], len1-k1, array2, len2, k-k1);
	} else 	if( array1[k1-1] == array2[k2-1] )
		return array1[k1-1];
}

13、寻找两个有序数组的中位数

寻找数组中的中位数，不能排序（用最大堆加最小堆可解决）

思路按照求第K小的思路实现

LeetCode：力扣

14、前 K 高频元素

LeetCode：力扣

15、查找重复数（LeetCode287）

（LeetCode287）给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

要求：
   1、不能更改原数组（假设数组是只读的）。
   2、只能使用额外的 O(1) 的空间。
   3、时间复杂度小于 O(n2) 。
   4、数组中只有一个重复的数字，但它可能不止重复出现一次。

思路：快慢指针原理简易解释

使用数组中的值作为索引下标进行遍历，遍历的结果肯定是一个环（有一个重复元素）
检测重复元素问题转换成检测环的入口
为了找到环的入口，可以进行如下步骤：

1、设置两个快慢指针， fast每次走两步，slow每次走一步，最终走了slow走了n步与fast相遇，fast走了2*n，fast可能比slow多饶了环的 i 圈，得到环的周长为 n/i （这个 i 不需要知道，只要知道相遇时 n 是环的整数倍）（注意此时的n不是指数组的长度）
2、slow指针继续走，且另设第三个指针从起点位置开始每次走一步，两个指针必定在入口处相遇

假设环的入口和起点的距离时m，此时 slow指针走的距离是 n，slow指针在环内，具体环内位置不知
当第三个指针走了m步到环的入口时
slow刚好走了n + m步，换句话说slow走了 m步（起点到入口的距离）+ n步，饶了环 i 圈（环的周长为n/i），此时slow又到了环的入口位置
得到相遇的是环的入口，入口元素即为重复元素。


int findDuplicate(vector<int>& nums) {
	
	int fast = 0, slow = 0;
	while(true){
		fast = nums[nums[fast]];
		slow = nums[slow];
		if(fast == slow)
			break;
	}
	int finder = 0;
	while(true){
		finder = nums[finder];
		slow = nums[slow];
		if(slow == finder)
			break;        
	}
	return slow;
}

解释：力扣

力扣

16、计算任意（N-1）个数的组合中乘积最大的一组

动态规划解法： n个整数，求其中任意n-1个数的乘积中的最大的一个（不准用除法）_皮皮go的博客-CSDN博客

给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。

法一：

时间空间复杂度都为O(n)
s1[i]：从前往后遍历到 0到i-1 位置的乘积(0<=i<n)
s2[j]：从后往前遍历 i+1到n 位置的乘积(0<=j<n)

有Max={s[i]*t[i]}
最后遍历一遍找出 max 最大值

法二：

设这n个数的乘积为P

当P=0时，除去n个数中的一个0，计算剩下的数的乘积，记为Q：

当Q=0时，说明n个数中至少有两个0，不管怎么组合，n-1个数的乘积都为0

当Q>0时，说明n个数中只有一个0，此时的Q当然是所要的乘积最大的结果

当Q<0时，说明n个数中只有一个0，但是除去0剩下的数的积为负数，所以还不如把0留下让乘积结果为0

当P>0时，从n个数中剔除最小的正数后所得的n-1个数的乘积即为最大值

当P<0时，从n个数中剔除绝对值最小的负数后所得的n-1个数的乘积即为最大值


/*方法1：
s[i]表示0到i-1乘积，t[i]表示i+1到n乘积，有Max={s[i]*t[i]}
*/
long caculate(int arr[],int length){
	long maxV=LONG_MIN;
	long *s=new long[length+1];
	long *t=new long[length+1];
	s[0]=1,t[length-1]=1;
	for(int i=1;i<=length;++i)
		s[i]=s[i-1]*arr[i-1];
	for(int i=length-2;i>=0;--i){
		t[i]=t[i+1]*arr[i+1];
	}
	for(int i=0;i<length;++i)maxV=max(maxV,s[i]*t[i]);
	delete[] s;
	delete[] t;
	return maxV;
}
/*方法2：
统计数组中正负零的个数
*/
long caculate2(int arr[],int length){
	long multi=1;       //结果
	bool flag=false;    //标识，数组中去掉的只能是一个数
	int opt=0,neg=0,zero=0;//正负零的个数
	int minO=INT_MAX；  //最小的正数
	int maxN=INT_MIN;   //最大的负数
	for(int i=0;i<length;i++){
		if(arr[i]<0){
			neg++;
			maxN=max(maxN,arr[i]);
		} else if(arr[i]>0){
			opt++;
			minO=min(minO,arr[i]);
		}
		else {
			zero++;
		}
	}
	
	// 大于1个0
	if(zero>1) {
		return 0;
	}
 
	//1个0的情况
	if(zero==1){
	    // 如果奇数个负数，最大是0
		if(neg%2 == 1) {
			return 0;
		}
		else{
	    // 如果偶数个负数，则直接输出n-1个数乘积
			for(int i=0;i<length;++i)
				if(arr[i]!=0)
					multi*=arr[i];
			return multi;
		}
	}
	
	// 下面是没有0的情况
	//有奇数个负数，去掉最大的负数，即绝对值最小的负数
	if(neg%2 == 1){
		for(int i=0;i<length;++i){
		    // flag 防止 重复数
			if(arr[i]!= maxN||flag){
				multi*=arr[i];
			}
			else flag=true;
		}
		return multi;
	}
	//有偶数个负数，去掉最小的正数
	for(int i=0;i<length;++i){
		if(arr[i]!=minO||flag){
			multi*=arr[i];
		}
		else flag=true;
	}
	return multi;
}

17、滑动窗口的最大值

分析查看：【剑指Offer】64、滑动窗口的最大值 - gzshan - 博客园


public ArrayList<Integer> maxInWindows(int [] num, int size){
	/*
	思路：用双端队列实现
	size window 大小
	queue.peek() 都是用来返回队列的头元素，不删除
	queue.poll() 从队列头部删除一个元素
	queue 中存放的是数组的index 方便计数
	queue 的长度不能大于 window 的size
	*/
	ArrayList<Integer> res=new ArrayList<>();
	if(num==null || num.length<1 || size<=0 || size>num.length)
		return res;
	Deque<Integer> queue=new LinkedList<>();
	for(int i=0;i<num.length;i++){
	    
		// 当加入第 i 个元素后，queue的长度为 (i-queue.peek() + 1)
		// 如果  (i-queue.peek() + 1) > size 时候，queue头元素，超出范围去掉
		while(!queue.isEmpty() && (i-queue.peek() + 1) > size) 
			 queue.poll();
		//当前值大于之前的值，之前的不可能是最大值，可以删掉
		while(!queue.isEmpty() && num[i]>=num[queue.getLast()]) 
			 queue.removeLast();
		queue.add(i);
		// 数组从0开始，当 i=size-1 时，queue中正好有size个元素
		if(i>=size-1){ //此时开始是第一个滑动窗口
			res.add(num[queue.peek()]);
		}
	}
	return res;
}

用队列做，需要看：面试题65. 滑动窗口的最大值_两鬓已不能斑白的博客-CSDN博客_滑动窗口的最大值

18、数组分成m段求各段和的最大值最小是多少

参考： https://www.cnblogs.com/debugxw/p/11461746.html

例如：a=[10,6,2,7,3],M=2,答案为16，两段分为[10,6][2,7,3]

问题描述
把一个包含n个正整数的序列划分成m个连续的子序列。设第i个序列的各数之和为S(i)，求所有S(i)的最大值最小是多少？

例子：
序列1 2 3 2 5 4划分为3个子序列的最优方案为 1 2 3 | 2 5 | 4，其中S(1),S(2),S(3)分别为6，7，4，那么最大值为7；
如果划分为 1 2 | 3 2 | 5 4，则最大值为9，不是最小。
解题思路
我们对问题做一些转化：
在一次划分中，求一个x，使得x满足：对任意的S(i)，都有S(i)<=x；这个条件保证了x是所有S(i)中的最大值。我们需要求的就是满足该条件的最小的x。

有了这个思路之后，我们继续分析如何找到这个x，首先，可以知道的是，max <= x <= sum。

接下来先是最朴素的想法：枚举每一个x，贪心地每次从左向右尽量多划分元素，但是S(i)不能超过x，而且划分的子序列个数不能超过m个（即所用划分线不能超过m-1条）

以上方法当然可行，但是每个x都遍历一次太浪费时间了。

问题经过转化，现在变成了在[max, sum]中间查找一个满足条件的x，查找的问题，相信大家对二分搜索并不陌生。这个时候，用二分搜索的思想来求x，效率一下子就上来了。


int max = 数组元素中的最大值;
int sum = 数组所有元素之和; 	
 
 
int binary_solve()
{
	int x=max; //要寻找的数
    int y=sum;  
	while(x<y)
	{
		int findmin = x+(y-x)/2; //要查找的 --- 最大值的最小化
		
		//如果能找到满足条件的划分，则最小化的值在 x 和 findmin 之间，否则 在  findmin+1 和y之间
		if(is_part(findmin)) 
		{
			y=findmin; //如果找到
		}
		else 
		{
			x=findmin+1;  //不能划分，则在findmin+1 和y之间查找
		}
			
	}
	return x;
}
 
//是否能把序列划分为每个序列之和不大于x的m个子序列 
bool is_part(int x)
{
	//每次往右划分，划分完后，所用的划分线不大于m-1个即可
	int line=0,s=0;
 
	for(int i=0;i<n;i++)
	{
		//假如有其中一个元素大于x，则极端地把划分线分别设在在其左边和右边，
		//都不能使这一个只有一个元素的序列之和不大于x，更不用说所有序列之和不大于x 
		//如果 x 从 arry[maxn] 为初始值的话，就用不到这个判断了
		if(arry[i]>x)
		{
			return false;
		}
		// 如果和大于，就不能再把当前元素加上了 ，因此在arry[i-1],arry[i]之间做划分
		// arry[i] 就分到下一个分组了
		if(s+arry[i] > x)
		{
			line++;   //此处多用了一条横杠
			s = arry[i];  //此时arry[i] 作为下一个分组的开始
			if(t>m-1) //t=m 时退出，即在最后一个元素之前都已经用了m条划分线，此时已把序列划分成了m+1个序列，太过分了，让其适可而止 
			{
				return false;
			}
		}
		else
		{
			s+=arry[i];//把当前元素与前面的元素连上，以便尽量往右划分，贪心到底 
		}
	}
	return true;
}

19、丑数

求第n个丑数--coding_ytusdc的博客-CSDN博客

【剑指Offer】33、丑数

【剑指Offer】33、丑数 - gzshan - 博客园

20、二分查找:


/**
 * 二分查找，找到该值在数组中的下标，否则为-1
 */
static int binarySerach(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
 
    // 这里必须是 <=  “=” 时才能取到mid值
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            return mid;
        }
        else if (array[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
 
    return -1;
}

　每次移动left和right指针的时候，需要在mid的基础上+1或者-1，防止出现死循环，程序也就能够正确的运行。

二分查找及其变体：https://www.jianshu.com/p/d29603b4ed02

变体：利用二分查找寻找满足条件的区间

普通二分查找：二分查找(Binary Search) - 程序员姜戈 - 博客园

21、有序数组，给定k，找到 k的最后一次出现的索引

[1，2，3，7，8，8，8，9]

解法：1、暴力法遍历数组就好

2、二分查找，因为有序，找到 pos 左右，从pos 开始左右遍历


int binarySerach(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
 
    int pos;
 
    // 这里必须是 <=  “=” 时才能取到mid值
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            pos = mid;
        }
        else if (array[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    
   //上面是二分查找
 
   //最后一次出现的位置
	for(int i=pos; i<=right; i++) {
		if(array[i] == key)
		{
			pos = i;
		}
		else {
			return pos;
		}
	}
	
	// 第一次出现的位置
	for(int i=pos; i >=0; i--) {
		if(array[i] == key)
		{
			pos = i;
		}
		else {
			return pos;
		}
	} 
}

22、给定两个队列，实现一个栈的功能；

用两个队列实现一个栈的功能操作C++_YangXueChina的博客-CSDN博客_c++两个队列实现一个栈

23、岛屿数量问题

这个解释比较清晰：

力扣

官方题解：力扣


void dfs(char[][] grid, int r, int c) {
	int nr = grid.length;
	int nc = grid[0].length;
	
	//  判断坐标 (r, c) 是否在网格中
	if (r < 0 || c < 0 || r >= nr || c >= nc) {
		return;
	}
	
	// 如果这个格子不是岛屿，直接返回
	if( grid[r][c] != 1) {
		return;
	}
 
	grid[r][c] = '2';  // 将格子标记为「已遍历过」
	dfs(grid, r - 1, c);
	dfs(grid, r + 1, c);
	dfs(grid, r, c - 1);
	dfs(grid, r, c + 1);
}
 
public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0) {
		return 0;
	}
 
	int nr = grid.length;
	int nc = grid[0].length;
	int num_islands = 0;
	for (int r = 0; r < nr; ++r) {
		for (int c = 0; c < nc; ++c) {
			if (grid[r][c] == '1') {
				++num_islands;
				dfs(grid, r, c);
			}
		}
	}
 
	return num_islands;
}

23、二维数值中查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：二维数组中，从左到右，从上到下是递增的，所以可以从将目标数从右上角开始遍历，如果当前数小于目标数，就向下遍历，如果当前数大于目标数就向左遍历。直到遍历完整个二维数组。


   public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return false;
        }//如果二维数组为空，或者行数为0，或者列数为0，那么直接返回false
        int rows=matrix.length;//
        int cols=matrix[0].length;
        int r=0;//设置起始点，从右上角的第一个数开始遍历。
        int c=cols-1;//列下标比列数少1
        while(r<=rows-1 &&c>=0){//只要行下标不超过二维数组的行数，列下标不小于列数。
            if(matrix[r][c] == target){//如果找到目标值就返回true
                return true;
            }
            else if(matrix[r][c] < target){ //如果遍历到的数值比目标值小，就往下一行遍历
                r++;
            }
            else{//如果遍历的数值比目标值大，就往同一行中左边的列遍历。
                c--;
            }
        }
        return false;//遍历完整个二维数组之后没有找到目标值，说明目标值不在这个二维数字中，返回false。
    }

24、1-N的自然数中，少了一个，找出这个数

- 有一个长度为n的数组，元素都是[1, n]且无重复，这时随机删除一个元素，1）求删除元素，2）要求时间复杂度O(n)，空间O(1)，3）不能改变数组

1）用1+2+...+n减去当前输入数据的总和。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

2）用12...*n除以当前输入数据的总积。时间复杂度：O(n) 空间复杂度：O(1) 【容易溢出】

3）用1^2^...^n的结果在逐个异或当前输入数据。时间复杂度：O(n) 空间复杂度：O(1)

异或方法：

Y＝1^2^3...^N，然后遍历数列每次异或当前的数字，最后剩下的就是要求的数字

任何数异或自己都等于0，任何数异或0都等于他自己


public int find_Miss_Number_By_XOR(int array[]) {
	int result = 0;
	
	for (int i = 0; i < array.length; i++) {
		result = result  ^ array[i];
	}
	
	int N = array.length；
	for (int i = 1; i <= N; i++) {
		result=result^(i);
	}
	return result;
 
}

扩展：如果删除两个元素呢，找到这两个元素


vector<int> missingTwo(vector<int>& nums) {
	vector<int> res;
	//法二 分组求和
	int N = nums.size()+2;
	int sumN = 0,sumNum = 0,sumLess_Num=0,sumLess_N=0;
	for(auto num : nums)
		sumNum += num;
	for(int i=1;i<=N;i++)
		sumN += i;
	// sumTwo是两个数的和
	int sumTwo = sumN - sumNum;
	// 求两个数和的一半,那么两个缺失得数一个大于diff，一个小于diff。
	int diff = (sumTwo)/2;
	//针对 N 和sum两个数组，小于等diff的分别分为一组；大于diff的分别分为一组；那么两个组的差值即为缺失的一大一小
	for(auto num : nums){
		if(num<=diff){
			sumLess_Num += num;
		}
	}
	
	for(int i=1;i<=N;i++){
		if(i<=diff){
			sumLess_N += i;
		}
	}
	res.push_back(sumLess_N-sumLess_Num);
	res.push_back(sumTwo-(sumLess_N-sumLess_Num));
	return res;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/163992