从数组中选择四条边形成的矩形的最大面积

2024 年 8 月 28 日 | 3 分钟阅读

给定一组代表长度的 n 个正整数。确定从给定数组中选择四条边可以形成的最大可能面积。需要注意的是，只有当给定数组包含两对相等的值时，才能形成一个矩形。

示例

Input : arr[] = {2, 1, 2, 5, 4, 4}
Output : 8
Explanation : Dimension will be 4 * 2

Input : arr[] = {2, 1, 3, 5, 4, 4}
Output : 0
Explanation : No rectangle possible

方法 1（排序）

该任务基本上归结为在数组中查找两对相等的值。如果存在多于两对，则选择值最大的两对。一种简单的解决方案是执行以下操作。

对给定数组进行排序。
从大到小遍历数组，并返回值最大的两对。

C++ 程序

// CPP program for finding maximum area possible
// of a rectangle
#include <bits/stdc++.h>
using namespace std;

// function for finding max area
int findArea(int arr[], int n)
{
	// sort array in non-increasing order
	sort(arr, arr + n, greater<int>());

	// Initialize two sides of rectangle
	int dimension[2] = { 0, 0 };

	// traverse through array
	for (int i = 0, j = 0; i < n - 1 && j < 2; i++)

		// if any element occurs twice
		// store that as dimension
		if (arr[i] == arr[i + 1])
			dimension[j++] = arr[i++];

	// return the product of dimensions
	return (dimension[0] * dimension[1]);
}

// driver function
int main()
{
	int arr[] = { 4, 2, 1, 4, 6, 6, 2, 5 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << findArea(arr, n);
	return 0;
}

输出

时间复杂度： O (n Log n)

方法 2（哈希）

在哈希集中，插入所有元素的第一次出现。跟踪不超过两次出现的值。

C++ 程序

// CPP program for finding maximum area possible
// of a rectangle
#include <bits/stdc++.h>
using namespace std;

// function for finding max area
int findArea(int arr[], int n)
{
	unordered_set<int> s;

	// traverse through array
	int first = 0, second = 0;
	for (int i = 0; i < n; i++) {

		// If this is first occurrence of arr[i],
		// simply insert and continue
		if (s.find(arr[i]) == s.end()) {
			s.insert(arr[i]);
			continue;
		}

		// If this is second (or more) occurrence,
		// update first and second maximum values.
		if (arr[i] > first) {
			second = first;
			first = arr[i];
		} else if (arr[i] > second)
			second = arr[i];
	}

	// return the product of dimensions
	return (first * second);
}

// driver function
int main()
{
	int arr[] = { 4, 2, 1, 4, 6, 6, 2, 5 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << findArea(arr, n);
	return 0;
}

输出

时间复杂度： O (n)

下一主题根到叶路径上的最大不同节点数

从数组中选择四条边形成的矩形的最大面积

示例

方法 1（排序）

C++ 程序

方法 2（哈希）

C++ 程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

从数组中选择四条边形成的矩形的最大面积

示例

方法 1（排序）

C++ 程序

方法 2（哈希）

C++ 程序

相关帖子

使用栈实现队列

计算二叉树中的非叶子节点数量

搜索查询自动完成

在平衡 BST 中查找和为给定对

二叉索引树范围更新和范围查询

将循环列表分成两半

最小堆和最大堆的区别

查找二叉树节点层级的公式

检测有向图中的循环

逆序数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器