本文概述
- C ++
- Java
- Python3
例子:
输入:A [] = {1000, 100, 10, 1}方法:
输出:100 10 1 1000
说明:
原始数组A [] = {1000, 100, 10, 1}
最终数组B [] = {100, 10, 1 , 1000}
大小为1的子集:
A [0] = 1000 B [0] = 100
A [1] = 100 B [1] = 10
A [2] = 10 B [2] = 1
A [3] = 1 B [3] = 1000
大小为2的子集:
{A [0], A [1]} = 1100 {B [0], B [1]} = 110
{A [0], A [2]} = 1010 {B [0], B [2]} = 101
{A [1], A [2]} = 110 {B [1], B [2]} = 11
....
同样, 所有相同的索引大小为2的子集的总和不同。
大小3的子集:
{A [0], A [1], A [2]} = 1110 {B [0], B [1], B [2]} = 111
{A [0], A [2 ], A [3]} = 1011 {B [0], B [2], B [3]} = 1101
{A [1], A [2], A [3]} = 111 {B [1] , B [2], B [3]} = 1011
因此, 没有相同索引的子集具有相等的总和。
输入:A [] = {1, 2, 3, 4, 5}
输出:5 1 2 3 4
这个想法是用一个较小的元素简单地替换除一个数组元素以外的所有数组元素。请按照以下步骤解决问题:
- 成对存储数组元素{A [i], i}.
- 按升序对对数组元素
- 现在, 遍历排序的顺序, 并将每个元素插入其下一个更大元素的原始索引(即, 在索引处)v [(i + 1)%n]。秒)。这样可以确保除索引之外的每个索引现在都具有比其中存储的先前值小的元素。
证明:令S = {arr1, arr2, …, arrk}是子集。如果u最初不属于S, 则在将u插入S时, 子集的总和发生变化。同样, 如果u属于S, 则让S’包含S中不存在的所有元素。这意味着u不属于S’。然后, 根据上述相同的理由, 子集S’的总和与其原始总和不同。下面是上述方法的实现:
C ++
//C++ Program to implement
//the above approach
#include <
bits/stdc++.h>
using namespace std;
//Function to rearrange the array such
//that no same-indexed subset have sum
//equal to that in the original array
void printNewArray(vector<
int>
a, int n)
{
//Initialize a vector
vector<
pair<
int , int>
>
v;
//Iterate the array
for ( int i = 0;
i <
n;
i++) {
v.push_back({ a[i], i });
}
//Sort the vector
sort(v.begin(), v.end());
int ans[n];
//Shift of elements to the
//index of its next cyclic element
for ( int i = 0;
i <
n;
i++) {
ans[v[(i + 1) % n].second]
= v[i].first;
}
//Print the answer
for ( int i = 0;
i <
n;
i++) {
cout <
<
ans[i] <
<
" " ;
}
}
//Driver Code
int main()
{
vector<
int>
a = { 4, 1, 2, 5, 3 };
int n = a.size();
printNewArray(a, n);
return 0;
}
Java
//Java program to implement
//the above approach
import java.io.*;
import java.util.*;
class GFG{static class pair
{
int first, second;
pair( int first, int second)
{
this .first = first;
this .second = second;
}
}
//Function to rearrange the array such
//that no same-indexed subset have sum
//equal to that in the original array
static void printNewArray(List<
Integer>
a, int n)
{//Initialize a vector
List<
pair>
v = new ArrayList<
>
();
//Iterate the array
for ( int i = 0 ;
i <
n;
i++)
{
v.add( new pair(a.get(i), i));
}//Sort the vector
Collections.sort(v, (pair s1, pair s2) ->
{
return s1.first - s2.first;
});
int ans[] = new int [n];
//Shift of elements to the
//index of its next cyclic element
for ( int i = 0 ;
i <
n;
i++)
{
ans[v.get((i + 1 ) % n).second] = v.get(i).first;
}//Print the answer
for ( int i = 0 ;
i <
n;
i++)
{
System.out.print(ans[i] + " " );
}
}
//Driver Code
public static void main(String args[])
{
List<
Integer>
a = Arrays.asList( 4 , 1 , 2 , 5 , 3 );
int n = a.size();
printNewArray(a, n);
}
}
//This code is contributed by offbeat
Python3
# Python3 Program to implement
# the above approach
# Function to rearrange the array such
# that no same-indexed subset have sum
# equal to that in the original array
def printNewArray(a, n):
# Initialize a vector
v = []
# Iterate the array
for i in range (n):
v.append((a[i], i ))# Sort the vector
v.sort()
ans = [ 0 ] * n
# Shift of elements to the
# index of its next cyclic element
for i in range (n):
ans[v[(i + 1 ) % n][ 1 ]] = v[i][ 0 ]# Print the answer
for i in range (n):
print (ans[i], end = " " )
# Driver Code
if __name__ = = "__main__" :
a = [ 4 , 1 , 2 , 5 , 3 ]
n = len (a)
printNewArray(a, n)
# This code is contributed by Chitranayal
输出如下:
3 5 1 4 2
时间复杂度:O(NLogN)
【重新排列数组,使索引相同的子集的总和与原始数组中的总和不同】辅助空间:O(N)
推荐阅读
- PHP上传进度条实现详细示例
- 按照数组中出现元素的顺序对链表进行排序
- 硬实时和软实时系统之间有什么区别()
- 算法题(最大的按行和按列排序的子矩阵)
- u盘打开盘自制,教您如何迅速自制一个PE系统
- u盘装系统工具,教您u盘怎样安装win7系统
- 7彩虹u盘打开,教您7彩虹主板怎样设置u盘打开
- 昂达u盘打开,教您昂达主板BIOS怎样设置u盘打开
- usb鼠标接触不良,教您usb鼠标接触不良